Ćwiczenia/3. Ćwiczenia/Zadanie 6. (Struktura ze wstawianiem i odczytem mediany w czasie O(log n)).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Proszę przedstawić W jaki sposób zrealizować strukturę danych, która pozwala wykonywać operacje:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Insert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. RemoveMedian (wyciągnięcie mediany)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### tak, żeby wszystkie operacje działały w czasie $ O(log(n)) $."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Plan działania"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Naszym celem jest podział zbioru wartości, z którego mamy wyznaczyć medianę, na 2 podzbiory, z których jeden będzie zawierał wartości mniejsze od mediany, a drugi większe od mediany (mediana może należeć do jednego z nich - wyjaśnienie później). Na myśl nasuwa się posortowanie tablicy, ale nie o to chodzi w tym zadaniu, bo musimy zapewnić, że wstawianie do struktury zajmie czas $ O(log(n)) $ oraz odczyt mediany również $ O(log(n)) $. Przedstawione wymagania, dotyczące pożądanej złożoności obliczeniowej, sugerują nam od razu zastosowanie struktury, dla której operacja wstawiania i usuwania wartości ma złożoność $ O(log(n)) $, a więc skorzystanie z kopca binarnego. Ponieważ planujemy podział wartości na 2 (prawie) równe (mogą się różnić o 1 element) podzbiory, potrzebne nam będą 2 kopce. Najłatwiej osiągniemy pożądany efekt, budując nową strukturę w taki sposób, by korzystała zarówno z kopca Max Heap, jak i Min Heap."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Przejdźmy teraz do omówienia, jaka jest logika dzialania tego algorytmu. Ponieważ Max Heap umieszcza wartość największą w swoim korzeniu, a Min Heap wartość najmniejszą, Max Heap musi zawierać tę połowę (lub blisko połowę) wartości, które są mniejsze od mediany (oraz ewentualnie również medianę), a Min Heap - wartości od niej większe (lub również medianę, jeżeli nie ma jej w Max Heapie)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tworzenie struktury zajmie czas $ O(n \\cdot log(n)) $. Postępujemy tak, że przeprowadzamy iterację przez sekwencję wartości, podejmując decyzję, do którego kopca \"wrzucić\" bieżącą wartość. Ponieważ założyliśmy, że kopiec Min Heap ma wartości większe, jeżeli bieżąca wartość jest większa od wartości najmniejszej w Min Heapie, musimy bieżącą wartość wrzucić do Min Heapa, natomiast, w przeciwnym wypadku, wartość wrzucamy do Max Heapa (ponieważ jest mniejsza od najmniejszej wartości spośród wartości największych (około połowy wartości)). Po każdym takim wstawieniu konieczne jest sprawdzenie, czy nasza struktura jest nadal zbalansowana (czy różnica między liczbą elementów w Min Heapie a liczbą elementów w Max Heapie jest nie większa niż 1). Jeżeli okaże się, że jest niezbalansowana, musimy z większego obecnie kopca zabrać roota i przerzucić do drugiego kopca (oczywiście taka operacja wymaga zbalansowania obu kopców, dlatego najlepiej posłużyć się wcześniej poznaną implementacją strkuktury kopca)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Poza zaimplementowaniem metod/funkcji, zwracających medianę i dodających wartość do struktrury, zaimplementowałem również usuwanie mediany (nie jest to częścią zadania)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Funkcja pomocnicza formatująca kompletne drzewo binarne"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def complete_tree_string(values):\n",
    "    if values:\n",
    "        just = 0\n",
    "        data = []\n",
    "\n",
    "        limit = 1\n",
    "        values_row = []\n",
    "        branches_row = []\n",
    "        prev_nodes = 0\n",
    "\n",
    "        for i in range(1, len(values) + 1):\n",
    "            curr_nodes = i - prev_nodes\n",
    "            val_str = str(values[i-1])\n",
    "            just = max(just, len(val_str))\n",
    "            values_row.append(val_str)\n",
    "            right_child_idx = 2 * i\n",
    "            left_child_idx = right_child_idx - 1\n",
    "            if left_child_idx < len(values):\n",
    "                branches_row.append('/')\n",
    "            if right_child_idx < len(values):\n",
    "                branches_row.append('\\\\')\n",
    "\n",
    "            if curr_nodes == limit: \n",
    "                prev_nodes = i\n",
    "                limit *= 2\n",
    "                data.append([values_row, branches_row])\n",
    "                values_row = []\n",
    "                branches_row = []\n",
    "\n",
    "        if values_row:\n",
    "            data.append([values_row, branches_row])\n",
    "\n",
    "        begin_sep = sep = 3 if just % 2 else 2\n",
    "        data_iter = iter(data[::-1])\n",
    "        result = [''] * (len(data) * 2 - 1)\n",
    "        result[-1] = (' ' * sep).join(val.center(just) for val in next(data_iter)[0])\n",
    "\n",
    "        # Format the tree string\n",
    "        for i, (values, branches) in enumerate(data_iter):\n",
    "            mul = 2 * i + 1\n",
    "            # Values\n",
    "            indent = (2 ** (i + 1) - 1) * (just + begin_sep) // 2\n",
    "            sep = 2 * sep + just\n",
    "            result[-(mul + 2)] = f\"{' ' * indent}{(' ' * sep).join(val.center(just) for val in values)}\"\n",
    "            # Branches\n",
    "            branch_indent = (3 * indent + just) // 4\n",
    "            branches_row = []\n",
    "            d_indent = indent - branch_indent\n",
    "            branches_sep = ' ' * (2 * (d_indent - 1) + just)\n",
    "            for i in range(0, len(branches), 2):\n",
    "                branches_row.append(f\"{branches[i]}{branches_sep}{branches[i + 1] if i + 1 < len(branches) else ''}\")\n",
    "            result[-(mul + 1)] = f\"{' ' * branch_indent}{(' ' * (sep - 2 * d_indent)).join(branches_row)}\"\n",
    "\n",
    "        return '\\n'.join(result)\n",
    "    else:\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu (obiektowa)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap:\n",
    "    def __init__(self, values=None):\n",
    "        self.heap = []\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self.heap)\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def insert(self, val: object):\n",
    "        # Add a value as the last node of out Complete Binary Tree\n",
    "        self.heap.append(val)\n",
    "        # Fix heap in order to satisfy a max-heap property\n",
    "        self._heapify_up(self.heap_size - 1)\n",
    "        \n",
    "    def get_max(self) -> object:\n",
    "        return None if not self.heap else self.heap[0]\n",
    "        \n",
    "    def remove_max(self) -> object:\n",
    "        if self.heap_size == 0:\n",
    "            raise IndexError(f'remove_max from an empty {self.__class__.__name__}')\n",
    "        # Store a value to be returned\n",
    "        removed = self.heap[0]\n",
    "        # Place the last leaf in the root position\n",
    "        last = self.heap.pop()\n",
    "        if self.heap_size > 0:\n",
    "            self.heap[0] = last\n",
    "            # Fix a heap in order to stisfy a max-heap property\n",
    "            self._heapify_down(0, self.heap_size)\n",
    "        return removed\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0): \n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            if self.heap[curr_idx] > self.heap[parent_idx]:\n",
    "                self.swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx):\n",
    "        # Loop till the current node has a child larger than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # smaller than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a max-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            largest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] > self.heap[curr_idx]: \n",
    "                    largest_idx = l\n",
    "                if r < end_idx and self.heap[r] > self.heap[largest_idx]:\n",
    "                    largest_idx = r\n",
    "\n",
    "            if largest_idx != curr_idx:\n",
    "                self.swap(curr_idx, largest_idx)\n",
    "                curr_idx = largest_idx\n",
    "            else:\n",
    "                break\n",
    "\n",
    "\n",
    "class MinHeap:\n",
    "    def __init__(self):\n",
    "        self.heap = []\n",
    "    \n",
    "    def __bool__(self):\n",
    "        return bool(self.heap)\n",
    "    \n",
    "    @property\n",
    "    def heap_size(self):\n",
    "        return len(self.heap)\n",
    "    \n",
    "    @staticmethod\n",
    "    def parent_idx(curr_idx):\n",
    "        return (curr_idx - 1) // 2\n",
    "    \n",
    "    @staticmethod\n",
    "    def left_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 1\n",
    "    \n",
    "    @staticmethod\n",
    "    def right_child_idx(curr_idx):\n",
    "        return curr_idx * 2 + 2\n",
    "    \n",
    "    def insert(self, val: object):\n",
    "        # Add a value as the last node of our Complete Binary Tree\n",
    "        self.heap.append(val)\n",
    "        # Fix heap in order to satisfy a min-heap property\n",
    "        self._heapify_up(self.heap_size - 1)\n",
    "        \n",
    "    def get_min(self) -> object:\n",
    "        return None if not self.heap else self.heap[0]\n",
    "        \n",
    "    def remove_min(self) -> object:\n",
    "        if self.heap_size == 0:\n",
    "            raise IndexError(f'remove_min from an empty {self.__class__.__name__}')\n",
    "        # Store a value to be returned\n",
    "        removed = self.heap[0]\n",
    "        # Place the last leaf in the root position\n",
    "        last = self.heap.pop()\n",
    "        if self.heap_size > 0:\n",
    "            self.heap[0] = last\n",
    "            # Fix a heap in order to stisfy a min-heap property\n",
    "            self._heapify_down(0, self.heap_size)\n",
    "        return removed\n",
    "    \n",
    "    def swap(self, i, j):\n",
    "        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]\n",
    "        \n",
    "    def _heapify_up(self, curr_idx, end_idx=0):\n",
    "        while curr_idx > end_idx:\n",
    "            parent_idx = self.parent_idx(curr_idx)\n",
    "            if self.heap[curr_idx] < self.heap[parent_idx]:\n",
    "                self.swap(curr_idx, parent_idx)\n",
    "            curr_idx = parent_idx\n",
    "        \n",
    "    def _heapify_down(self, curr_idx, end_idx): \n",
    "        # Loop till the current node has a child smaller than itself\n",
    "        # We assume that when we enter a node which both children are\n",
    "        # larger than this node, a subtree which a current node is a\n",
    "        # root of must fulfill a min-heap property\n",
    "        while True:\n",
    "            l = self.left_child_idx(curr_idx)\n",
    "            r = self.right_child_idx(curr_idx)\n",
    "            smallest_idx = curr_idx\n",
    "\n",
    "            if l < end_idx:\n",
    "                if self.heap[l] < self.heap[curr_idx]: \n",
    "                    smallest_idx = l\n",
    "                if r < end_idx and self.heap[r] < self.heap[smallest_idx]:\n",
    "                    smallest_idx = r\n",
    "\n",
    "            if smallest_idx != curr_idx:\n",
    "                self.swap(curr_idx, smallest_idx)\n",
    "                curr_idx = smallest_idx\n",
    "            else:\n",
    "                break\n",
    "\n",
    "            \n",
    "class MedianHeap:\n",
    "    def __init__(self, values=[]):\n",
    "        self.min_heap = MinHeap()\n",
    "        self.max_heap = MaxHeap()\n",
    "        for val in values:\n",
    "            self.insert(val)\n",
    "            \n",
    "    def __str__(self):\n",
    "        max_str = complete_tree_string(self.max_heap.heap)\n",
    "        min_str = complete_tree_string(self.min_heap.heap)\n",
    "        return f\"Max Heap:\\n{max_str}\\n\\nMin Heap:\\n{min_str}\"\n",
    "        \n",
    "    def __len__(self):\n",
    "        return self.max_heap.heap_size + self.min_heap.heap_size\n",
    "    \n",
    "    def insert(self, val: object):  # O(log n)\n",
    "        # If no value is stored in this data structure or a value inserted\n",
    "        # is greater than the lowest value of the Min Heap, insert this value\n",
    "        # to the Min Heap\n",
    "        if not self or val > self.min_heap.get_min():\n",
    "            self.min_heap.insert(val)\n",
    "        # Add a value to the Max Heap in other cases\n",
    "        else:\n",
    "            self.max_heap.insert(val)\n",
    "        # Make heaps have the same (differing only by one element) sizes\n",
    "        self._rebalance_heaps()\n",
    "            \n",
    "    def get_median(self):  # O(1)\n",
    "        # If there are more element in the min_heap, our set of\n",
    "        # values has odd number of values and median is this heap's root\n",
    "        if self.min_heap.heap_size < self.max_heap.heap_size:\n",
    "            return self.max_heap.get_max()\n",
    "        # If the Max Heap is bigger, its root is a median\n",
    "        elif self.min_heap.heap_size > self.max_heap.heap_size:\n",
    "            return self.min_heap.get_min()\n",
    "        # If we have even number of elements\n",
    "        elif self:\n",
    "            res = (self.max_heap.get_max() + self.min_heap.get_min()) / 2\n",
    "            return int(res) if res == int(res) else res\n",
    "        # If there is no value stored in this data structure\n",
    "        else:\n",
    "            return None\n",
    "    \n",
    "    # Note that we don't have to rebalance our structure after removing a median\n",
    "    # That's because if a structure has odd number of values, the one from the\n",
    "    # greater heap will be removed, thus both heaps will have the same size at\n",
    "    # the end. In next removals roots of both heaps will be removed as our \n",
    "    # structure has now even number of values stored.\n",
    "    def remove_median(self):  # O(log n)\n",
    "        # If there are more element in the min_heap, our set of\n",
    "        # values has odd number of values and median is this heap's root\n",
    "        if self.min_heap.heap_size < self.max_heap.heap_size:\n",
    "            return self.max_heap.remove_max()\n",
    "        # If the Max Heap is bigger, its root is a median\n",
    "        elif self.min_heap.heap_size > self.max_heap.heap_size:\n",
    "            return self.min_heap.remove_min()\n",
    "        # If we have even number of elements\n",
    "        elif self:\n",
    "            res = (self.max_heap.remove_max() + self.min_heap.remove_min()) / 2\n",
    "            return int(res) if res == int(res) else res\n",
    "        else:\n",
    "            raise IndexError(f'remove_median from an empty {self.__class__.__name__}')\n",
    "        \n",
    "    def _rebalance_heaps(self):\n",
    "        d_size = self.min_heap.heap_size - self.max_heap.heap_size \n",
    "        # If the Min Heap has greater size by more than one element than\n",
    "        # the Max Heap, move its root to the Max Heap\n",
    "        if d_size > 1:\n",
    "            self.max_heap.insert(self.min_heap.remove_min())\n",
    "        # On the other hand, id the Max Heap is greater in size by more than\n",
    "        # one element than the Min Heap, move its root to the Min Heap\n",
    "        elif d_size < -1:\n",
    "            self.min_heap.insert(self.max_heap.remove_max())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST #1:\n",
      "Input: [3, 64, 51, 53, 96, 64, 39, 20, 82, 19, 17, 35, 9, 23, 95, 73]\n",
      "Sorted: [3, 9, 17, 19, 20, 23, 35, 39, 51, 53, 64, 64, 73, 82, 95, 96]\n",
      "Length: 16\n",
      "Expected 45.0\n",
      "Result: 45\n",
      "Total passed to tested ratio: 1/1\n",
      "\n",
      "TEST #2:\n",
      "Input: [85, 93, 63, 33, 59, 21, 76, 41, 55, 75]\n",
      "Sorted: [21, 33, 41, 55, 59, 63, 75, 76, 85, 93]\n",
      "Length: 10\n",
      "Expected 61.0\n",
      "Result: 61\n",
      "Total passed to tested ratio: 2/2\n",
      "\n",
      "TEST #3:\n",
      "Input: [49, 57, 45, 61, 91, 79, 63, 60, 86, 77, 65, 27, 23, 100, 11, 19, 37]\n",
      "Sorted: [11, 19, 23, 27, 37, 45, 49, 57, 60, 61, 63, 65, 77, 79, 86, 91, 100]\n",
      "Length: 17\n",
      "Expected 60\n",
      "Result: 60\n",
      "Total passed to tested ratio: 3/3\n",
      "\n",
      "TEST #4:\n",
      "Input: [55, 7, 18, 58, 20, 72, 58, 11, 54, 20, 37, 87, 50, 25, 20, 98, 18, 49]\n",
      "Sorted: [7, 11, 18, 18, 20, 20, 20, 25, 37, 49, 50, 54, 55, 58, 58, 72, 87, 98]\n",
      "Length: 18\n",
      "Expected 43.0\n",
      "Result: 43\n",
      "Total passed to tested ratio: 4/4\n",
      "\n",
      "TEST #5:\n",
      "Input: [53, 98, 58]\n",
      "Sorted: [53, 58, 98]\n",
      "Length: 3\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 5/5\n",
      "\n",
      "TEST #6:\n",
      "Input: [54, 44, 54, 51, 57, 44, 82, 20, 52, 59, 48, 94, 69, 38, 99, 10, 27, 70, 92, 47]\n",
      "Sorted: [10, 20, 27, 38, 44, 44, 47, 48, 51, 52, 54, 54, 57, 59, 69, 70, 82, 92, 94, 99]\n",
      "Length: 20\n",
      "Expected 53.0\n",
      "Result: 53\n",
      "Total passed to tested ratio: 6/6\n",
      "\n",
      "TEST #7:\n",
      "Input: [0, 32, 38, 31, 30, 51, 75, 100, 98, 20, 71, 39, 31, 14, 33, 88, 14, 79, 33, 48, 32, 59, 93, 34, 71, 83, 93, 24]\n",
      "Sorted: [0, 14, 14, 20, 24, 30, 31, 31, 32, 32, 33, 33, 34, 38, 39, 48, 51, 59, 71, 71, 75, 79, 83, 88, 93, 93, 98, 100]\n",
      "Length: 28\n",
      "Expected 38.5\n",
      "Result: 38.5\n",
      "Total passed to tested ratio: 7/7\n",
      "\n",
      "TEST #8:\n",
      "Input: [20, 83, 100, 51, 38, 26, 75, 18, 4, 60, 77, 12, 73, 10, 42, 49, 87, 5, 68, 46, 48, 52, 16, 29, 74, 67, 45]\n",
      "Sorted: [4, 5, 10, 12, 16, 18, 20, 26, 29, 38, 42, 45, 46, 48, 49, 51, 52, 60, 67, 68, 73, 74, 75, 77, 83, 87, 100]\n",
      "Length: 27\n",
      "Expected 48\n",
      "Result: 48\n",
      "Total passed to tested ratio: 8/8\n",
      "\n",
      "TEST #9:\n",
      "Input: [6, 94, 15, 54, 81, 95, 66, 53, 34, 3, 92, 67, 57, 25, 59, 90, 60, 53, 60, 29]\n",
      "Sorted: [3, 6, 15, 25, 29, 34, 53, 53, 54, 57, 59, 60, 60, 66, 67, 81, 90, 92, 94, 95]\n",
      "Length: 20\n",
      "Expected 58.0\n",
      "Result: 58\n",
      "Total passed to tested ratio: 9/9\n",
      "\n",
      "TEST #10:\n",
      "Input: [66, 52, 90]\n",
      "Sorted: [52, 66, 90]\n",
      "Length: 3\n",
      "Expected 66\n",
      "Result: 66\n",
      "Total passed to tested ratio: 10/10\n",
      "\n",
      "TEST #11:\n",
      "Input: [9, 8, 60, 66, 39, 65, 88, 80, 19, 79]\n",
      "Sorted: [8, 9, 19, 39, 60, 65, 66, 79, 80, 88]\n",
      "Length: 10\n",
      "Expected 62.5\n",
      "Result: 62.5\n",
      "Total passed to tested ratio: 11/11\n",
      "\n",
      "TEST #12:\n",
      "Input: [88, 6, 50, 99, 25, 8, 72, 87, 98, 46, 79, 67, 49, 24, 75, 6, 41, 48, 24, 50, 20]\n",
      "Sorted: [6, 6, 8, 20, 24, 24, 25, 41, 46, 48, 49, 50, 50, 67, 72, 75, 79, 87, 88, 98, 99]\n",
      "Length: 21\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 12/12\n",
      "\n",
      "TEST #13:\n",
      "Input: [66]\n",
      "Sorted: [66]\n",
      "Length: 1\n",
      "Expected 66\n",
      "Result: 66\n",
      "Total passed to tested ratio: 13/13\n",
      "\n",
      "TEST #14:\n",
      "Input: [84, 45, 84, 87, 15, 87, 78, 63, 28, 65, 51, 88, 61, 29, 64, 64, 74, 66, 41, 87, 22, 14, 27, 74, 96, 86, 39]\n",
      "Sorted: [14, 15, 22, 27, 28, 29, 39, 41, 45, 51, 61, 63, 64, 64, 65, 66, 74, 74, 78, 84, 84, 86, 87, 87, 87, 88, 96]\n",
      "Length: 27\n",
      "Expected 64\n",
      "Result: 64\n",
      "Total passed to tested ratio: 14/14\n",
      "\n",
      "TEST #15:\n",
      "Input: [32, 20, 84, 82, 35, 59, 72, 24, 90, 91, 6, 58, 68, 32, 43, 9, 17, 58, 90, 93, 58]\n",
      "Sorted: [6, 9, 17, 20, 24, 32, 32, 35, 43, 58, 58, 58, 59, 68, 72, 82, 84, 90, 90, 91, 93]\n",
      "Length: 21\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 15/15\n",
      "\n",
      "TEST #16:\n",
      "Input: [74, 90, 15, 50, 46, 38, 88, 55, 81, 24, 51, 58, 17, 50, 99, 24, 78, 46, 16, 69, 13]\n",
      "Sorted: [13, 15, 16, 17, 24, 24, 38, 46, 46, 50, 50, 51, 55, 58, 69, 74, 78, 81, 88, 90, 99]\n",
      "Length: 21\n",
      "Expected 50\n",
      "Result: 50\n",
      "Total passed to tested ratio: 16/16\n",
      "\n",
      "TEST #17:\n",
      "Input: [49, 22, 11, 44, 56, 7, 27]\n",
      "Sorted: [7, 11, 22, 27, 44, 49, 56]\n",
      "Length: 7\n",
      "Expected 27\n",
      "Result: 27\n",
      "Total passed to tested ratio: 17/17\n",
      "\n",
      "TEST #18:\n",
      "Input: [43, 82, 12, 8, 97, 48, 63, 23, 26, 68, 62, 69, 25, 70]\n",
      "Sorted: [8, 12, 23, 25, 26, 43, 48, 62, 63, 68, 69, 70, 82, 97]\n",
      "Length: 14\n",
      "Expected 55.0\n",
      "Result: 55\n",
      "Total passed to tested ratio: 18/18\n",
      "\n",
      "TEST #19:\n",
      "Input: [60, 82, 22, 39, 96, 78, 69, 32, 46, 34, 13, 81, 67, 46, 85, 2, 35, 79, 20, 46]\n",
      "Sorted: [2, 13, 20, 22, 32, 34, 35, 39, 46, 46, 46, 60, 67, 69, 78, 79, 81, 82, 85, 96]\n",
      "Length: 20\n",
      "Expected 46.0\n",
      "Result: 46\n",
      "Total passed to tested ratio: 19/19\n",
      "\n",
      "TEST #20:\n",
      "Input: [16, 60, 73]\n",
      "Sorted: [16, 60, 73]\n",
      "Length: 3\n",
      "Expected 60\n",
      "Result: 60\n",
      "Total passed to tested ratio: 20/20\n",
      "\n",
      "TEST #21:\n",
      "Input: [5, 92, 59, 71, 10, 70, 0, 0, 10, 88, 42, 90, 67, 9, 38, 48, 81, 73, 45, 100, 42, 80, 100, 13, 33, 28]\n",
      "Sorted: [0, 0, 5, 9, 10, 10, 13, 28, 33, 38, 42, 42, 45, 48, 59, 67, 70, 71, 73, 80, 81, 88, 90, 92, 100, 100]\n",
      "Length: 26\n",
      "Expected 46.5\n",
      "Result: 46.5\n",
      "Total passed to tested ratio: 21/21\n",
      "\n",
      "TEST #22:\n",
      "Input: [32, 53, 42, 56, 74, 99, 100, 44, 46, 55, 96, 88, 42, 70, 6, 90, 65, 28, 63, 99, 64]\n",
      "Sorted: [6, 28, 32, 42, 42, 44, 46, 53, 55, 56, 63, 64, 65, 70, 74, 88, 90, 96, 99, 99, 100]\n",
      "Length: 21\n",
      "Expected 63\n",
      "Result: 63\n",
      "Total passed to tested ratio: 22/22\n",
      "\n",
      "TEST #23:\n",
      "Input: [72]\n",
      "Sorted: [72]\n",
      "Length: 1\n",
      "Expected 72\n",
      "Result: 72\n",
      "Total passed to tested ratio: 23/23\n",
      "\n",
      "TEST #24:\n",
      "Input: [40, 35]\n",
      "Sorted: [35, 40]\n",
      "Length: 2\n",
      "Expected 37.5\n",
      "Result: 37.5\n",
      "Total passed to tested ratio: 24/24\n",
      "\n",
      "TEST #25:\n",
      "Input: [2, 28, 94, 81, 86, 38, 9, 87, 78, 80, 23, 5, 29, 28]\n",
      "Sorted: [2, 5, 9, 23, 28, 28, 29, 38, 78, 80, 81, 86, 87, 94]\n",
      "Length: 14\n",
      "Expected 33.5\n",
      "Result: 33.5\n",
      "Total passed to tested ratio: 25/25\n",
      "\n",
      "TEST #26:\n",
      "Input: [95, 80, 90, 52, 78, 82, 96, 20, 56, 56, 33, 86, 66, 56]\n",
      "Sorted: [20, 33, 52, 56, 56, 56, 66, 78, 80, 82, 86, 90, 95, 96]\n",
      "Length: 14\n",
      "Expected 72.0\n",
      "Result: 72\n",
      "Total passed to tested ratio: 26/26\n",
      "\n",
      "TEST #27:\n",
      "Input: [73, 56, 75]\n",
      "Sorted: [56, 73, 75]\n",
      "Length: 3\n",
      "Expected 73\n",
      "Result: 73\n",
      "Total passed to tested ratio: 27/27\n",
      "\n",
      "TEST #28:\n",
      "Input: [63, 14, 2, 4, 74, 24, 16, 37, 28, 42, 25, 71, 33, 27, 42, 96]\n",
      "Sorted: [2, 4, 14, 16, 24, 25, 27, 28, 33, 37, 42, 42, 63, 71, 74, 96]\n",
      "Length: 16\n",
      "Expected 30.5\n",
      "Result: 30.5\n",
      "Total passed to tested ratio: 28/28\n",
      "\n",
      "TEST #29:\n",
      "Input: [71, 40, 12, 56, 93, 56, 56, 90, 85, 19, 55, 24, 92, 62, 66, 20, 38]\n",
      "Sorted: [12, 19, 20, 24, 38, 40, 55, 56, 56, 56, 62, 66, 71, 85, 90, 92, 93]\n",
      "Length: 17\n",
      "Expected 56\n",
      "Result: 56\n",
      "Total passed to tested ratio: 29/29\n",
      "\n",
      "TEST #30:\n",
      "Input: [90, 38, 94, 24, 98, 45, 38]\n",
      "Sorted: [24, 38, 38, 45, 90, 94, 98]\n",
      "Length: 7\n",
      "Expected 45\n",
      "Result: 45\n",
      "Total passed to tested ratio: 30/30\n",
      "\n",
      "TEST #31:\n",
      "Input: [85, 6, 99, 91, 54, 81, 96, 14, 84, 46, 10, 38, 11, 39, 0, 45, 74, 97, 27, 96, 27, 73, 99, 81, 66, 31, 56, 24, 5]\n",
      "Sorted: [0, 5, 6, 10, 11, 14, 24, 27, 27, 31, 38, 39, 45, 46, 54, 56, 66, 73, 74, 81, 81, 84, 85, 91, 96, 96, 97, 99, 99]\n",
      "Length: 29\n",
      "Expected 54\n",
      "Result: 54\n",
      "Total passed to tested ratio: 31/31\n",
      "\n",
      "TEST #32:\n",
      "Input: [71, 60, 23, 19, 3, 30, 73, 67, 74, 77, 54, 69, 96, 81, 15, 100, 15, 27, 7, 65, 63, 47, 68, 3]\n",
      "Sorted: [3, 3, 7, 15, 15, 19, 23, 27, 30, 47, 54, 60, 63, 65, 67, 68, 69, 71, 73, 74, 77, 81, 96, 100]\n",
      "Length: 24\n",
      "Expected 61.5\n",
      "Result: 61.5\n",
      "Total passed to tested ratio: 32/32\n",
      "\n",
      "TEST #33:\n",
      "Input: [78, 4, 58, 55, 31, 37, 63, 39, 81, 84, 42, 85, 90, 100, 45, 29, 69, 52, 26, 22, 72]\n",
      "Sorted: [4, 22, 26, 29, 31, 37, 39, 42, 45, 52, 55, 58, 63, 69, 72, 78, 81, 84, 85, 90, 100]\n",
      "Length: 21\n",
      "Expected 55\n",
      "Result: 55\n",
      "Total passed to tested ratio: 33/33\n",
      "\n",
      "TEST #34:\n",
      "Input: [95, 40, 89, 97, 17, 91, 6, 47, 19, 39, 42, 19, 43, 28, 95, 42, 30, 44, 6, 31, 67, 63, 96, 53]\n",
      "Sorted: [6, 6, 17, 19, 19, 28, 30, 31, 39, 40, 42, 42, 43, 44, 47, 53, 63, 67, 89, 91, 95, 95, 96, 97]\n",
      "Length: 24\n",
      "Expected 42.5\n",
      "Result: 42.5\n",
      "Total passed to tested ratio: 34/34\n",
      "\n",
      "TEST #35:\n",
      "Input: [4, 23, 39, 32, 37, 73, 7]\n",
      "Sorted: [4, 7, 23, 32, 37, 39, 73]\n",
      "Length: 7\n",
      "Expected 32\n",
      "Result: 32\n",
      "Total passed to tested ratio: 35/35\n",
      "\n",
      "TEST #36:\n",
      "Input: [35, 53, 71, 12, 33, 11, 16, 45, 41, 82, 74, 67, 59, 7, 10, 40, 33, 15, 70, 24, 59, 22, 3, 33, 91, 24, 86, 59, 53]\n",
      "Sorted: [3, 7, 10, 11, 12, 15, 16, 22, 24, 24, 33, 33, 33, 35, 40, 41, 45, 53, 53, 59, 59, 59, 67, 70, 71, 74, 82, 86, 91]\n",
      "Length: 29\n",
      "Expected 40\n",
      "Result: 40\n",
      "Total passed to tested ratio: 36/36\n",
      "\n",
      "TEST #37:\n",
      "Input: [99, 10, 80, 69]\n",
      "Sorted: [10, 69, 80, 99]\n",
      "Length: 4\n",
      "Expected 74.5\n",
      "Result: 74.5\n",
      "Total passed to tested ratio: 37/37\n",
      "\n",
      "TEST #38:\n",
      "Input: [68]\n",
      "Sorted: [68]\n",
      "Length: 1\n",
      "Expected 68\n",
      "Result: 68\n",
      "Total passed to tested ratio: 38/38\n",
      "\n",
      "TEST #39:\n",
      "Input: [95, 94, 61, 35, 88, 73, 6, 95]\n",
      "Sorted: [6, 35, 61, 73, 88, 94, 95, 95]\n",
      "Length: 8\n",
      "Expected 80.5\n",
      "Result: 80.5\n",
      "Total passed to tested ratio: 39/39\n",
      "\n",
      "TEST #40:\n",
      "Input: [24, 27, 37, 70, 32, 93, 37, 81, 43, 22, 35, 91, 25, 45, 22, 28, 77, 100, 43, 41, 4, 71, 57]\n",
      "Sorted: [4, 22, 22, 24, 25, 27, 28, 32, 35, 37, 37, 41, 43, 43, 45, 57, 70, 71, 77, 81, 91, 93, 100]\n",
      "Length: 23\n",
      "Expected 41\n",
      "Result: 41\n",
      "Total passed to tested ratio: 40/40\n",
      "\n",
      "TEST #41:\n",
      "Input: [21, 27, 100, 79, 65, 32, 37, 12, 79, 73, 58, 89, 43, 10, 9, 2, 91, 25, 18, 90, 53, 11, 20, 29, 85, 10, 31, 100, 21, 26]\n",
      "Sorted: [2, 9, 10, 10, 11, 12, 18, 20, 21, 21, 25, 26, 27, 29, 31, 32, 37, 43, 53, 58, 65, 73, 79, 79, 85, 89, 90, 91, 100, 100]\n",
      "Length: 30\n",
      "Expected 31.5\n",
      "Result: 31.5\n",
      "Total passed to tested ratio: 41/41\n",
      "\n",
      "TEST #42:\n",
      "Input: [19, 65, 84, 90, 8, 90, 66, 34, 11, 64, 91, 98, 72, 49, 83, 92, 58, 35, 73, 33, 12, 14]\n",
      "Sorted: [8, 11, 12, 14, 19, 33, 34, 35, 49, 58, 64, 65, 66, 72, 73, 83, 84, 90, 90, 91, 92, 98]\n",
      "Length: 22\n",
      "Expected 64.5\n",
      "Result: 64.5\n",
      "Total passed to tested ratio: 42/42\n",
      "\n",
      "TEST #43:\n",
      "Input: [45, 86, 13, 12, 9, 53, 26, 81, 33, 53, 19, 84, 36, 19, 15, 26, 2]\n",
      "Sorted: [2, 9, 12, 13, 15, 19, 19, 26, 26, 33, 36, 45, 53, 53, 81, 84, 86]\n",
      "Length: 17\n",
      "Expected 26\n",
      "Result: 26\n",
      "Total passed to tested ratio: 43/43\n",
      "\n",
      "TEST #44:\n",
      "Input: [69, 84, 19, 43, 32, 94, 52, 59, 92, 57, 8, 72, 95, 67, 18, 22, 50, 95, 63, 28, 30, 9, 100, 31]\n",
      "Sorted: [8, 9, 18, 19, 22, 28, 30, 31, 32, 43, 50, 52, 57, 59, 63, 67, 69, 72, 84, 92, 94, 95, 95, 100]\n",
      "Length: 24\n",
      "Expected 54.5\n",
      "Result: 54.5\n",
      "Total passed to tested ratio: 44/44\n",
      "\n",
      "TEST #45:\n",
      "Input: [78, 63, 11, 89, 53, 68, 81, 4, 65, 18, 82, 53, 98, 80]\n",
      "Sorted: [4, 11, 18, 53, 53, 63, 65, 68, 78, 80, 81, 82, 89, 98]\n",
      "Length: 14\n",
      "Expected 66.5\n",
      "Result: 66.5\n",
      "Total passed to tested ratio: 45/45\n",
      "\n",
      "TEST #46:\n",
      "Input: [4, 85, 55, 6]\n",
      "Sorted: [4, 6, 55, 85]\n",
      "Length: 4\n",
      "Expected 30.5\n",
      "Result: 30.5\n",
      "Total passed to tested ratio: 46/46\n",
      "\n",
      "TEST #47:\n",
      "Input: [19, 56, 6, 47, 9, 59, 69, 1, 20, 67, 42, 18, 41, 52, 86]\n",
      "Sorted: [1, 6, 9, 18, 19, 20, 41, 42, 47, 52, 56, 59, 67, 69, 86]\n",
      "Length: 15\n",
      "Expected 42\n",
      "Result: 42\n",
      "Total passed to tested ratio: 47/47\n",
      "\n",
      "TEST #48:\n",
      "Input: [89, 1, 72, 61, 89, 47, 62, 23, 95, 40, 23, 76, 82, 45, 56, 50, 98, 69, 33, 1, 88, 14, 70, 71, 56]\n",
      "Sorted: [1, 1, 14, 23, 23, 33, 40, 45, 47, 50, 56, 56, 61, 62, 69, 70, 71, 72, 76, 82, 88, 89, 89, 95, 98]\n",
      "Length: 25\n",
      "Expected 61\n",
      "Result: 61\n",
      "Total passed to tested ratio: 48/48\n",
      "\n",
      "TEST #49:\n",
      "Input: [19, 66, 30, 51, 18, 11, 95, 98, 82, 53, 45, 65, 40, 32, 55]\n",
      "Sorted: [11, 18, 19, 30, 32, 40, 45, 51, 53, 55, 65, 66, 82, 95, 98]\n",
      "Length: 15\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 49/49\n",
      "\n",
      "TEST #50:\n",
      "Input: [59, 73, 94, 44, 75, 74, 94, 92, 49, 58, 100, 12, 79, 10]\n",
      "Sorted: [10, 12, 44, 49, 58, 59, 73, 74, 75, 79, 92, 94, 94, 100]\n",
      "Length: 14\n",
      "Expected 73.5\n",
      "Result: 73.5\n",
      "Total passed to tested ratio: 50/50\n",
      "\n",
      "TEST #51:\n",
      "Input: [72, 25, 95, 40, 31, 73, 12, 16, 33, 27, 3, 77, 77, 18, 18, 35, 73, 92, 2, 9, 11, 16, 93, 7, 24, 35, 42]\n",
      "Sorted: [2, 3, 7, 9, 11, 12, 16, 16, 18, 18, 24, 25, 27, 31, 33, 35, 35, 40, 42, 72, 73, 73, 77, 77, 92, 93, 95]\n",
      "Length: 27\n",
      "Expected 31\n",
      "Result: 31\n",
      "Total passed to tested ratio: 51/51\n",
      "\n",
      "TEST #52:\n",
      "Input: [17, 27, 66, 37, 72, 54, 62, 30, 25, 70, 33, 59, 90, 53, 7, 83, 18, 50, 84, 57, 71, 73, 35, 40, 5, 65, 44, 67, 68]\n",
      "Sorted: [5, 7, 17, 18, 25, 27, 30, 33, 35, 37, 40, 44, 50, 53, 54, 57, 59, 62, 65, 66, 67, 68, 70, 71, 72, 73, 83, 84, 90]\n",
      "Length: 29\n",
      "Expected 54\n",
      "Result: 54\n",
      "Total passed to tested ratio: 52/52\n",
      "\n",
      "TEST #53:\n",
      "Input: [88, 87, 40, 26, 58]\n",
      "Sorted: [26, 40, 58, 87, 88]\n",
      "Length: 5\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 53/53\n",
      "\n",
      "TEST #54:\n",
      "Input: [55, 83, 35, 16, 35, 73, 51, 42, 26, 70, 67, 15, 52, 6, 14, 5, 30, 75, 49, 76, 50]\n",
      "Sorted: [5, 6, 14, 15, 16, 26, 30, 35, 35, 42, 49, 50, 51, 52, 55, 67, 70, 73, 75, 76, 83]\n",
      "Length: 21\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 54/54\n",
      "\n",
      "TEST #55:\n",
      "Input: [2, 61, 32, 33, 2, 74, 16, 40, 22, 54, 31, 2, 59, 13, 29, 11, 97, 78, 74, 33, 80, 76, 61, 63, 93, 66, 57, 15, 60, 93]\n",
      "Sorted: [2, 2, 2, 11, 13, 15, 16, 22, 29, 31, 32, 33, 33, 40, 54, 57, 59, 60, 61, 61, 63, 66, 74, 74, 76, 78, 80, 93, 93, 97]\n",
      "Length: 30\n",
      "Expected 55.5\n",
      "Result: 55.5\n",
      "Total passed to tested ratio: 55/55\n",
      "\n",
      "TEST #56:\n",
      "Input: []\n",
      "Sorted: []\n",
      "Length: 0\n",
      "Expected None\n",
      "Result: None\n",
      "Total passed to tested ratio: 56/56\n",
      "\n",
      "TEST #57:\n",
      "Input: [6, 59, 85, 36, 23, 52, 4, 11, 38, 40, 54, 9, 13, 43, 26, 87, 64]\n",
      "Sorted: [4, 6, 9, 11, 13, 23, 26, 36, 38, 40, 43, 52, 54, 59, 64, 85, 87]\n",
      "Length: 17\n",
      "Expected 38\n",
      "Result: 38\n",
      "Total passed to tested ratio: 57/57\n",
      "\n",
      "TEST #58:\n",
      "Input: [75, 65, 31, 67, 92, 85, 68, 98, 91, 50, 50, 47, 5, 73, 42, 5, 58, 21, 18, 0, 98, 44, 55, 66, 31, 8, 68, 72, 37]\n",
      "Sorted: [0, 5, 5, 8, 18, 21, 31, 31, 37, 42, 44, 47, 50, 50, 55, 58, 65, 66, 67, 68, 68, 72, 73, 75, 85, 91, 92, 98, 98]\n",
      "Length: 29\n",
      "Expected 55\n",
      "Result: 55\n",
      "Total passed to tested ratio: 58/58\n",
      "\n",
      "TEST #59:\n",
      "Input: [95, 18, 97, 56, 10]\n",
      "Sorted: [10, 18, 56, 95, 97]\n",
      "Length: 5\n",
      "Expected 56\n",
      "Result: 56\n",
      "Total passed to tested ratio: 59/59\n",
      "\n",
      "TEST #60:\n",
      "Input: [0, 20, 81, 54, 1, 67, 68, 64, 18, 14, 72, 34, 27, 3, 97, 90, 6, 16]\n",
      "Sorted: [0, 1, 3, 6, 14, 16, 18, 20, 27, 34, 54, 64, 67, 68, 72, 81, 90, 97]\n",
      "Length: 18\n",
      "Expected 30.5\n",
      "Result: 30.5\n",
      "Total passed to tested ratio: 60/60\n",
      "\n",
      "TEST #61:\n",
      "Input: [35, 33]\n",
      "Sorted: [33, 35]\n",
      "Length: 2\n",
      "Expected 34.0\n",
      "Result: 34\n",
      "Total passed to tested ratio: 61/61\n",
      "\n",
      "TEST #62:\n",
      "Input: [94, 54, 19, 13, 58, 96, 89, 72, 79, 55, 63, 51]\n",
      "Sorted: [13, 19, 51, 54, 55, 58, 63, 72, 79, 89, 94, 96]\n",
      "Length: 12\n",
      "Expected 60.5\n",
      "Result: 60.5\n",
      "Total passed to tested ratio: 62/62\n",
      "\n",
      "TEST #63:\n",
      "Input: [98, 34, 45, 45, 56, 20, 15, 61, 39, 92, 12, 57, 50, 58, 80, 49, 61, 79, 29, 82, 46, 54, 79, 20, 26, 22, 37]\n",
      "Sorted: [12, 15, 20, 20, 22, 26, 29, 34, 37, 39, 45, 45, 46, 49, 50, 54, 56, 57, 58, 61, 61, 79, 79, 80, 82, 92, 98]\n",
      "Length: 27\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 63/63\n",
      "\n",
      "TEST #64:\n",
      "Input: [39, 37, 54, 61, 14, 78, 0, 89, 47, 73, 9, 52, 78, 28, 64, 57, 15, 28, 46, 24]\n",
      "Sorted: [0, 9, 14, 15, 24, 28, 28, 37, 39, 46, 47, 52, 54, 57, 61, 64, 73, 78, 78, 89]\n",
      "Length: 20\n",
      "Expected 46.5\n",
      "Result: 46.5\n",
      "Total passed to tested ratio: 64/64\n",
      "\n",
      "TEST #65:\n",
      "Input: [78, 3, 40, 10, 14, 39, 44, 50, 10, 63, 36, 66, 12, 57, 0, 42, 43, 3, 73, 54, 45, 12, 14, 19, 62, 17]\n",
      "Sorted: [0, 3, 3, 10, 10, 12, 12, 14, 14, 17, 19, 36, 39, 40, 42, 43, 44, 45, 50, 54, 57, 62, 63, 66, 73, 78]\n",
      "Length: 26\n",
      "Expected 39.5\n",
      "Result: 39.5\n",
      "Total passed to tested ratio: 65/65\n",
      "\n",
      "TEST #66:\n",
      "Input: [14, 42, 61, 73, 15, 36, 55, 23, 86, 32, 25]\n",
      "Sorted: [14, 15, 23, 25, 32, 36, 42, 55, 61, 73, 86]\n",
      "Length: 11\n",
      "Expected 36\n",
      "Result: 36\n",
      "Total passed to tested ratio: 66/66\n",
      "\n",
      "TEST #67:\n",
      "Input: [17, 6, 77, 57, 81, 0, 45, 92, 27, 0, 3, 61, 59, 46, 74, 14, 74, 74, 46, 61, 1, 70, 42]\n",
      "Sorted: [0, 0, 1, 3, 6, 14, 17, 27, 42, 45, 46, 46, 57, 59, 61, 61, 70, 74, 74, 74, 77, 81, 92]\n",
      "Length: 23\n",
      "Expected 46\n",
      "Result: 46\n",
      "Total passed to tested ratio: 67/67\n",
      "\n",
      "TEST #68:\n",
      "Input: [59, 64, 49, 27, 62, 25, 10, 46, 33, 45, 83, 42, 66, 30, 2, 25, 71, 74, 29]\n",
      "Sorted: [2, 10, 25, 25, 27, 29, 30, 33, 42, 45, 46, 49, 59, 62, 64, 66, 71, 74, 83]\n",
      "Length: 19\n",
      "Expected 45\n",
      "Result: 45\n",
      "Total passed to tested ratio: 68/68\n",
      "\n",
      "TEST #69:\n",
      "Input: [7, 72, 58, 17, 19, 63, 38, 77, 6, 81, 11, 73, 9, 26, 95, 63, 49]\n",
      "Sorted: [6, 7, 9, 11, 17, 19, 26, 38, 49, 58, 63, 63, 72, 73, 77, 81, 95]\n",
      "Length: 17\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 69/69\n",
      "\n",
      "TEST #70:\n",
      "Input: [3, 35, 48, 52, 90, 51, 8, 92, 59, 93, 47, 65, 0, 85]\n",
      "Sorted: [0, 3, 8, 35, 47, 48, 51, 52, 59, 65, 85, 90, 92, 93]\n",
      "Length: 14\n",
      "Expected 51.5\n",
      "Result: 51.5\n",
      "Total passed to tested ratio: 70/70\n",
      "\n",
      "TEST #71:\n",
      "Input: [29, 43, 37, 4, 55, 53, 48, 59, 37, 16, 68, 89, 60, 70, 20, 75, 50, 100, 86]\n",
      "Sorted: [4, 16, 20, 29, 37, 37, 43, 48, 50, 53, 55, 59, 60, 68, 70, 75, 86, 89, 100]\n",
      "Length: 19\n",
      "Expected 53\n",
      "Result: 53\n",
      "Total passed to tested ratio: 71/71\n",
      "\n",
      "TEST #72:\n",
      "Input: [47, 27, 83, 19, 61, 51, 57, 19, 23, 54, 63]\n",
      "Sorted: [19, 19, 23, 27, 47, 51, 54, 57, 61, 63, 83]\n",
      "Length: 11\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 72/72\n",
      "\n",
      "TEST #73:\n",
      "Input: [40, 36, 47, 29, 86, 45, 92, 99, 78]\n",
      "Sorted: [29, 36, 40, 45, 47, 78, 86, 92, 99]\n",
      "Length: 9\n",
      "Expected 47\n",
      "Result: 47\n",
      "Total passed to tested ratio: 73/73\n",
      "\n",
      "TEST #74:\n",
      "Input: [19, 26, 61, 75, 46, 33, 54, 94, 100, 40, 57, 16, 14, 87, 28, 71, 40, 80, 46, 96, 69, 13, 25, 86, 58, 13]\n",
      "Sorted: [13, 13, 14, 16, 19, 25, 26, 28, 33, 40, 40, 46, 46, 54, 57, 58, 61, 69, 71, 75, 80, 86, 87, 94, 96, 100]\n",
      "Length: 26\n",
      "Expected 50.0\n",
      "Result: 50\n",
      "Total passed to tested ratio: 74/74\n",
      "\n",
      "TEST #75:\n",
      "Input: [49, 0, 20, 7]\n",
      "Sorted: [0, 7, 20, 49]\n",
      "Length: 4\n",
      "Expected 13.5\n",
      "Result: 13.5\n",
      "Total passed to tested ratio: 75/75\n",
      "\n",
      "TEST #76:\n",
      "Input: [94]\n",
      "Sorted: [94]\n",
      "Length: 1\n",
      "Expected 94\n",
      "Result: 94\n",
      "Total passed to tested ratio: 76/76\n",
      "\n",
      "TEST #77:\n",
      "Input: [92, 73, 23, 76, 1, 96, 86, 96, 9]\n",
      "Sorted: [1, 9, 23, 73, 76, 86, 92, 96, 96]\n",
      "Length: 9\n",
      "Expected 76\n",
      "Result: 76\n",
      "Total passed to tested ratio: 77/77\n",
      "\n",
      "TEST #78:\n",
      "Input: [100, 89, 51, 77, 72, 76, 13]\n",
      "Sorted: [13, 51, 72, 76, 77, 89, 100]\n",
      "Length: 7\n",
      "Expected 76\n",
      "Result: 76\n",
      "Total passed to tested ratio: 78/78\n",
      "\n",
      "TEST #79:\n",
      "Input: [35, 68, 11, 40, 73, 58, 75, 49, 85, 89, 100, 47, 34, 33]\n",
      "Sorted: [11, 33, 34, 35, 40, 47, 49, 58, 68, 73, 75, 85, 89, 100]\n",
      "Length: 14\n",
      "Expected 53.5\n",
      "Result: 53.5\n",
      "Total passed to tested ratio: 79/79\n",
      "\n",
      "TEST #80:\n",
      "Input: [5, 34, 61, 68, 13, 100, 80, 76]\n",
      "Sorted: [5, 13, 34, 61, 68, 76, 80, 100]\n",
      "Length: 8\n",
      "Expected 64.5\n",
      "Result: 64.5\n",
      "Total passed to tested ratio: 80/80\n",
      "\n",
      "TEST #81:\n",
      "Input: [1, 34, 8, 4, 77, 2, 38, 83, 8, 63, 78]\n",
      "Sorted: [1, 2, 4, 8, 8, 34, 38, 63, 77, 78, 83]\n",
      "Length: 11\n",
      "Expected 34\n",
      "Result: 34\n",
      "Total passed to tested ratio: 81/81\n",
      "\n",
      "TEST #82:\n",
      "Input: [0, 29, 66, 33, 75, 89, 52, 84, 3, 2, 35, 62, 23, 26, 76, 89, 72, 30, 96, 52, 8, 61, 93, 30, 47, 31, 52]\n",
      "Sorted: [0, 2, 3, 8, 23, 26, 29, 30, 30, 31, 33, 35, 47, 52, 52, 52, 61, 62, 66, 72, 75, 76, 84, 89, 89, 93, 96]\n",
      "Length: 27\n",
      "Expected 52\n",
      "Result: 52\n",
      "Total passed to tested ratio: 82/82\n",
      "\n",
      "TEST #83:\n",
      "Input: [65, 90, 93, 54, 7, 73, 9, 100, 26]\n",
      "Sorted: [7, 9, 26, 54, 65, 73, 90, 93, 100]\n",
      "Length: 9\n",
      "Expected 65\n",
      "Result: 65\n",
      "Total passed to tested ratio: 83/83\n",
      "\n",
      "TEST #84:\n",
      "Input: [8, 43, 69, 51, 82, 21, 0, 88, 1, 3, 50, 74, 77, 75, 82, 64, 36, 14, 76, 97, 20, 90, 55, 75, 100, 42]\n",
      "Sorted: [0, 1, 3, 8, 14, 20, 21, 36, 42, 43, 50, 51, 55, 64, 69, 74, 75, 75, 76, 77, 82, 82, 88, 90, 97, 100]\n",
      "Length: 26\n",
      "Expected 59.5\n",
      "Result: 59.5\n",
      "Total passed to tested ratio: 84/84\n",
      "\n",
      "TEST #85:\n",
      "Input: [7, 88, 25, 87, 22, 34, 22, 99, 21, 92, 99, 24, 42, 23, 6, 52, 70, 19, 66, 52, 55, 58]\n",
      "Sorted: [6, 7, 19, 21, 22, 22, 23, 24, 25, 34, 42, 52, 52, 55, 58, 66, 70, 87, 88, 92, 99, 99]\n",
      "Length: 22\n",
      "Expected 47.0\n",
      "Result: 47\n",
      "Total passed to tested ratio: 85/85\n",
      "\n",
      "TEST #86:\n",
      "Input: [58, 32, 10, 74, 67, 71, 82, 37, 19, 15, 62]\n",
      "Sorted: [10, 15, 19, 32, 37, 58, 62, 67, 71, 74, 82]\n",
      "Length: 11\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 86/86\n",
      "\n",
      "TEST #87:\n",
      "Input: [67, 0, 59, 58, 41, 55, 70, 98, 92, 3, 37, 92, 47, 48, 66, 44, 17, 21, 6, 11, 21, 96, 18]\n",
      "Sorted: [0, 3, 6, 11, 17, 18, 21, 21, 37, 41, 44, 47, 48, 55, 58, 59, 66, 67, 70, 92, 92, 96, 98]\n",
      "Length: 23\n",
      "Expected 47\n",
      "Result: 47\n",
      "Total passed to tested ratio: 87/87\n",
      "\n",
      "TEST #88:\n",
      "Input: [55, 23, 10, 58, 93, 41, 93, 72, 50, 77, 52, 25, 68, 69, 94, 100, 14, 57, 7, 69, 5, 81]\n",
      "Sorted: [5, 7, 10, 14, 23, 25, 41, 50, 52, 55, 57, 58, 68, 69, 69, 72, 77, 81, 93, 93, 94, 100]\n",
      "Length: 22\n",
      "Expected 57.5\n",
      "Result: 57.5\n",
      "Total passed to tested ratio: 88/88\n",
      "\n",
      "TEST #89:\n",
      "Input: [53, 51, 78, 61, 70, 58, 35, 19, 66, 69, 10, 77, 93, 50, 38, 79, 89, 22]\n",
      "Sorted: [10, 19, 22, 35, 38, 50, 51, 53, 58, 61, 66, 69, 70, 77, 78, 79, 89, 93]\n",
      "Length: 18\n",
      "Expected 59.5\n",
      "Result: 59.5\n",
      "Total passed to tested ratio: 89/89\n",
      "\n",
      "TEST #90:\n",
      "Input: [67, 57, 85, 24, 71, 76, 63, 84, 71, 25, 61, 6, 83, 60]\n",
      "Sorted: [6, 24, 25, 57, 60, 61, 63, 67, 71, 71, 76, 83, 84, 85]\n",
      "Length: 14\n",
      "Expected 65.0\n",
      "Result: 65\n",
      "Total passed to tested ratio: 90/90\n",
      "\n",
      "TEST #91:\n",
      "Input: [3, 28, 68, 46, 51]\n",
      "Sorted: [3, 28, 46, 51, 68]\n",
      "Length: 5\n",
      "Expected 46\n",
      "Result: 46\n",
      "Total passed to tested ratio: 91/91\n",
      "\n",
      "TEST #92:\n",
      "Input: [100]\n",
      "Sorted: [100]\n",
      "Length: 1\n",
      "Expected 100\n",
      "Result: 100\n",
      "Total passed to tested ratio: 92/92\n",
      "\n",
      "TEST #93:\n",
      "Input: [58, 22, 72, 64, 24, 47, 70, 36, 63, 97, 32, 90, 65, 19, 33, 36, 10, 32, 85, 92, 68, 58, 92, 85, 41, 41, 81, 34, 15, 6]\n",
      "Sorted: [6, 10, 15, 19, 22, 24, 32, 32, 33, 34, 36, 36, 41, 41, 47, 58, 58, 63, 64, 65, 68, 70, 72, 81, 85, 85, 90, 92, 92, 97]\n",
      "Length: 30\n",
      "Expected 52.5\n",
      "Result: 52.5\n",
      "Total passed to tested ratio: 93/93\n",
      "\n",
      "TEST #94:\n",
      "Input: [6, 17, 14, 55, 11, 37, 13, 99, 77, 79, 17, 54, 100, 81, 2, 8, 48, 74, 1, 42, 5, 11, 60]\n",
      "Sorted: [1, 2, 5, 6, 8, 11, 11, 13, 14, 17, 17, 37, 42, 48, 54, 55, 60, 74, 77, 79, 81, 99, 100]\n",
      "Length: 23\n",
      "Expected 37\n",
      "Result: 37\n",
      "Total passed to tested ratio: 94/94\n",
      "\n",
      "TEST #95:\n",
      "Input: [100, 65, 28, 75, 68, 96, 43, 19, 17, 31, 61, 100, 72, 70, 90]\n",
      "Sorted: [17, 19, 28, 31, 43, 61, 65, 68, 70, 72, 75, 90, 96, 100, 100]\n",
      "Length: 15\n",
      "Expected 68\n",
      "Result: 68\n",
      "Total passed to tested ratio: 95/95\n",
      "\n",
      "TEST #96:\n",
      "Input: [52, 14, 7, 10, 27, 21, 85, 87, 42, 2, 99, 37, 52, 60, 49, 66]\n",
      "Sorted: [2, 7, 10, 14, 21, 27, 37, 42, 49, 52, 52, 60, 66, 85, 87, 99]\n",
      "Length: 16\n",
      "Expected 45.5\n",
      "Result: 45.5\n",
      "Total passed to tested ratio: 96/96\n",
      "\n",
      "TEST #97:\n",
      "Input: [43, 53, 61, 85, 53, 36, 44, 44, 4, 89, 55, 92, 70, 33, 26, 39, 90, 38, 92, 16]\n",
      "Sorted: [4, 16, 26, 33, 36, 38, 39, 43, 44, 44, 53, 53, 55, 61, 70, 85, 89, 90, 92, 92]\n",
      "Length: 20\n",
      "Expected 48.5\n",
      "Result: 48.5\n",
      "Total passed to tested ratio: 97/97\n",
      "\n",
      "TEST #98:\n",
      "Input: [70, 85, 43, 61, 54, 20, 51, 28, 31, 58, 18, 68, 76, 47]\n",
      "Sorted: [18, 20, 28, 31, 43, 47, 51, 54, 58, 61, 68, 70, 76, 85]\n",
      "Length: 14\n",
      "Expected 52.5\n",
      "Result: 52.5\n",
      "Total passed to tested ratio: 98/98\n",
      "\n",
      "TEST #99:\n",
      "Input: [38, 9, 16, 77, 92, 50, 39]\n",
      "Sorted: [9, 16, 38, 39, 50, 77, 92]\n",
      "Length: 7\n",
      "Expected 39\n",
      "Result: 39\n",
      "Total passed to tested ratio: 99/99\n",
      "\n",
      "TEST #100:\n",
      "Input: [54, 31, 97, 72, 95, 20, 24, 1, 22, 65, 74]\n",
      "Sorted: [1, 20, 22, 24, 31, 54, 65, 72, 74, 95, 97]\n",
      "Length: 11\n",
      "Expected 54\n",
      "Result: 54\n",
      "Total passed to tested ratio: 100/100\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "samples = 100\n",
    "\n",
    "passed = 0\n",
    "for n in range(samples):\n",
    "    arr = [random.randint(0, 100) for _ in range(random.randint(0, 30))]\n",
    "    arr_sorted = sorted(arr)\n",
    "    center = len(arr) // 2\n",
    "    if len(arr) >= 2:\n",
    "        expected = arr_sorted[center] if len(arr) % 2 else (arr_sorted[center] + arr_sorted[center - 1]) / 2\n",
    "    elif len(arr) == 1:\n",
    "        expected = arr[0]\n",
    "    else:\n",
    "        expected = None\n",
    "    median_heap = MedianHeap(arr)\n",
    "    result = median_heap.get_median()\n",
    "    is_correct = result == expected\n",
    "    passed += is_correct\n",
    "    print(f'TEST #{n + 1}:')\n",
    "    print('Input:', arr)\n",
    "    print('Sorted:', sorted(arr))\n",
    "    print('Length:', len(arr))\n",
    "    print('Expected', expected)\n",
    "    print('Result:', result)\n",
    "    print(f'Total passed to tested ratio: {passed}/{n + 1}')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max Heap:\n",
      "      31\n",
      "     /  \\\n",
      "  24      20\n",
      "  /\\\n",
      "1   22\n",
      "\n",
      "Min Heap:\n",
      "      54\n",
      "     /  \\\n",
      "  65      74\n",
      "  /\\      /\n",
      "97  72  95\n",
      "\n",
      "Removed median: 54\n",
      "\n",
      "Max Heap:\n",
      "      31\n",
      "     /  \\\n",
      "  24      20\n",
      "  /\\\n",
      "1   22\n",
      "\n",
      "Min Heap:\n",
      "      65\n",
      "     /  \\\n",
      "  72      74\n",
      "  /\\\n",
      "97  95\n",
      "\n",
      "Removed median: 48\n",
      "\n",
      "Max Heap:\n",
      "      24\n",
      "     /  \\\n",
      "  22      20\n",
      "  /\n",
      "1 \n",
      "\n",
      "Min Heap:\n",
      "      72\n",
      "     /  \\\n",
      "  95      74\n",
      "  /\n",
      "97\n",
      "\n",
      "Removed median: 48\n",
      "\n",
      "Max Heap:\n",
      "  22\n",
      "  /\\\n",
      "1   20\n",
      "\n",
      "Min Heap:\n",
      "  74\n",
      "  /\\\n",
      "95  97\n",
      "\n",
      "Removed median: 48\n",
      "\n",
      "Max Heap:\n",
      "  20\n",
      "  /\n",
      "1 \n",
      "\n",
      "Min Heap:\n",
      "  95\n",
      "  /\n",
      "97\n",
      "\n",
      "Removed median: 57.5\n",
      "\n",
      "Max Heap:\n",
      "1\n",
      "\n",
      "Min Heap:\n",
      "97\n",
      "\n",
      "Removed median: 49\n",
      "\n"
     ]
    }
   ],
   "source": [
    "while median_heap:\n",
    "    print(median_heap)\n",
    "    print('\\nRemoved median:', median_heap.remove_median(), end='\\n\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Implementacja algorytmu (funkcyjna)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "_left = lambda i: 2 * i + 1\n",
    "_right = lambda i: 2 * i + 2\n",
    "_parent = lambda i: (i - 1) // 2\n",
    "\n",
    "\n",
    "def print_heap(heap: list, *args, **kwargs):\n",
    "    print(complete_tree_string(heap), *args, **kwargs)\n",
    "    \n",
    "    \n",
    "def _swap(heap: list, i, j):\n",
    "    heap[i], heap[j] = heap[j], heap[i]\n",
    "    \n",
    "\"\"\"\n",
    "Max Heap\n",
    "\"\"\"        \n",
    "def insert_to_max_heap(heap: list, val: object):\n",
    "    # Add a value as the last node of out Complete Binary Tree\n",
    "    heap.append(val)\n",
    "    # Fix heap in order to satisfy a max-heap property\n",
    "    _heapify_max_up(heap, len(heap) - 1)\n",
    "    \n",
    "    \n",
    "def remove_max_from_heap(heap: list) -> object:\n",
    "    if not heap:\n",
    "        raise IndexError(f'remove_max from an empty Max Heap')\n",
    "    # Store a value to be returned\n",
    "    removed = heap[0]\n",
    "    # Place the last leaf in the root position\n",
    "    last = heap.pop()\n",
    "    if heap:\n",
    "        heap[0] = last\n",
    "        # Fix a heap in order to stisfy a max-heap property\n",
    "        _heapify_max_down(heap, 0, len(heap))\n",
    "    return removed\n",
    "    \n",
    "    \n",
    "def _heapify_max_up(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index' = 0):\n",
    "    while curr_idx > end_idx:\n",
    "        parent_idx = _parent(curr_idx)\n",
    "        if heap[curr_idx] > heap[parent_idx]:\n",
    "            _swap(heap, curr_idx, parent_idx)\n",
    "        curr_idx = parent_idx\n",
    "            \n",
    "    \n",
    "def _heapify_max_down(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index'):\n",
    "    # Loop till the current node has a child larger than itself\n",
    "    # We assume that when we enter a node which both children are\n",
    "    # smaller than this node, a subtree which a current node is a\n",
    "    # root of must fulfill a max-heap property.\n",
    "    while True:\n",
    "        i = _left(curr_idx)\n",
    "        j = _right(curr_idx)\n",
    "        k = curr_idx\n",
    "        \n",
    "        if i < end_idx:\n",
    "            if heap[i] > heap[k]:\n",
    "                k = i\n",
    "            if j < end_idx and heap[j] > heap[k]:\n",
    "                k = j\n",
    "                \n",
    "        if k == curr_idx: return\n",
    "        # Swap the current with the largest child\n",
    "        heap[curr_idx], heap[k] = heap[k], heap[curr_idx]\n",
    "        curr_idx = k\n",
    "\n",
    "\"\"\"\n",
    "Min Heap\n",
    "\"\"\"         \n",
    "def insert_to_min_heap(heap: list, val: object):\n",
    "    # Add a value as the last node of our Complete Binary Tree\n",
    "    heap.append(val)\n",
    "    # Fix heap in order to satisfy a min-heap property\n",
    "    _heapify_min_up(heap, len(heap) - 1)\n",
    "    \n",
    "    \n",
    "def remove_min_from_heap(heap: list) -> object:\n",
    "    if not heap:\n",
    "        raise IndexError(f'remove_min from an empty Min Heap')\n",
    "    # Store a value to be returned\n",
    "    removed = heap[0]\n",
    "    # Place the last leaf in the root position\n",
    "    last = heap.pop()\n",
    "    if heap:\n",
    "        heap[0] = last\n",
    "        # Fix a heap in order to stisfy a min-heap property\n",
    "        _heapify_min_down(heap, 0, len(heap))\n",
    "    return removed\n",
    "    \n",
    "    \n",
    "def _heapify_min_up(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index' = 0):\n",
    "    while curr_idx > end_idx:\n",
    "        parent_idx = _parent(curr_idx)\n",
    "        if heap[curr_idx] < heap[parent_idx]:\n",
    "            _swap(heap, curr_idx, parent_idx)\n",
    "        curr_idx = parent_idx\n",
    "            \n",
    "    \n",
    "def _heapify_min_down(heap: list, curr_idx: 'heapify begin index', end_idx: 'heapify end index'):\n",
    "    # Loop till the current node has a child smaller than itself\n",
    "    # We assume that when we enter a node which both children are\n",
    "    # larger than this node, a subtree which a current node is a\n",
    "    # root of must fulfill a min-heap property\n",
    "    while True:\n",
    "        i = _left(curr_idx)\n",
    "        j = _right(curr_idx)\n",
    "        k = curr_idx\n",
    "        \n",
    "        if i < end_idx:\n",
    "            if heap[i] < heap[k]:\n",
    "                k = i\n",
    "            if j < end_idx and heap[j] < heap[k]:\n",
    "                k = j\n",
    "                \n",
    "        if k == curr_idx: return\n",
    "        # Swap the current with the smallest child\n",
    "        heap[curr_idx], heap[k] = heap[k], heap[curr_idx]\n",
    "        curr_idx = k\n",
    "        \n",
    "\"\"\"\n",
    "Median Heap\n",
    "\"\"\"   \n",
    "def create_median_heap(values: 'iterable') -> ('min_heap', 'max_heap'):\n",
    "    min_heap = []\n",
    "    max_heap = []\n",
    "    for val in values:\n",
    "        insert_to_median_heap(min_heap, max_heap, val)\n",
    "    return min_heap, max_heap\n",
    "\n",
    "\n",
    "def print_median_heap(min_heap: list, max_heap: list):\n",
    "    print(\"Max Heap\")\n",
    "    print_heap(max_heap, end='\\n\\n')\n",
    "    print(\"Min Heap\")\n",
    "    print_heap(min_heap)\n",
    "    \n",
    "    \n",
    "def insert_to_median_heap(min_heap: list, max_heap: list, val: object):\n",
    "    if not min_heap or min_heap[0] < val:\n",
    "        insert_to_min_heap(min_heap, val)\n",
    "    else:\n",
    "        insert_to_max_heap(max_heap, val)\n",
    "    _rebalance_median_heap(min_heap, max_heap)\n",
    "    \n",
    "\n",
    "def get_median_from_median_heap(min_heap: list, max_heap: list) -> 'median':\n",
    "    if len(min_heap) < len(max_heap):\n",
    "        return max_heap[0]\n",
    "    elif len(min_heap) > len(max_heap):\n",
    "        return min_heap[0]\n",
    "    elif min_heap and max_heap:\n",
    "        res = (min_heap[0] + max_heap[0]) / 2\n",
    "        return int(res) if int(res) == res else res\n",
    "    else:\n",
    "        return None\n",
    "           \n",
    "        \n",
    "def remove_median_from_median_heap(min_heap: list, max_heap: list) -> 'median':\n",
    "    if len(min_heap) < len(max_heap):\n",
    "        return remove_max_from_heap(max_heap)\n",
    "    elif len(min_heap) > len(max_heap):\n",
    "        return remove_min_from_heap(min_heap)\n",
    "    elif min_heap and max_heap:\n",
    "        res = (remove_max_from_heap(max_heap) + remove_min_from_heap(min_heap)) / 2\n",
    "        return int(res) if int(res) == res else res\n",
    "    else:\n",
    "        raise IndexError(f'remove_median from an empty median heap')\n",
    "\n",
    "        \n",
    "def _rebalance_median_heap(min_heap: list, max_heap: list):\n",
    "    d_size = len(min_heap) - len(max_heap)\n",
    "    if d_size > 1:\n",
    "        insert_to_max_heap(max_heap, remove_min_from_heap(min_heap))\n",
    "    elif d_size < -1:\n",
    "        insert_to_min_heap(min_heap, remove_max_from_heap(max_heap))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "###### Kilka testów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "TEST #1:\n",
      "Input: [88, 83, 58, 99, 50, 98, 81, 72, 96, 61, 4, 75, 10, 84, 67, 95, 34, 84, 39, 20, 35, 0, 71, 22]\n",
      "Sorted: [0, 4, 10, 20, 22, 34, 35, 39, 50, 58, 61, 67, 71, 72, 75, 81, 83, 84, 84, 88, 95, 96, 98, 99]\n",
      "Length: 24\n",
      "Expected 69.0\n",
      "Result: 69\n",
      "Total passed to tested ratio: 1/1\n",
      "\n",
      "TEST #2:\n",
      "Input: [61, 70, 78, 68, 63, 32, 59, 92, 74, 83, 9, 63, 38, 34, 86]\n",
      "Sorted: [9, 32, 34, 38, 59, 61, 63, 63, 68, 70, 74, 78, 83, 86, 92]\n",
      "Length: 15\n",
      "Expected 63\n",
      "Result: 63\n",
      "Total passed to tested ratio: 2/2\n",
      "\n",
      "TEST #3:\n",
      "Input: [63, 34, 11, 76, 79, 30, 30, 50, 63, 95, 24, 71, 61, 64, 28, 99, 93, 63]\n",
      "Sorted: [11, 24, 28, 30, 30, 34, 50, 61, 63, 63, 63, 64, 71, 76, 79, 93, 95, 99]\n",
      "Length: 18\n",
      "Expected 63.0\n",
      "Result: 63\n",
      "Total passed to tested ratio: 3/3\n",
      "\n",
      "TEST #4:\n",
      "Input: [86, 44, 17, 9, 4, 37, 7, 11, 58, 54, 46, 20, 23, 33, 73, 55, 1, 69, 8, 62, 71, 45, 37, 71, 51, 12, 59, 21, 43, 57]\n",
      "Sorted: [1, 4, 7, 8, 9, 11, 12, 17, 20, 21, 23, 33, 37, 37, 43, 44, 45, 46, 51, 54, 55, 57, 58, 59, 62, 69, 71, 71, 73, 86]\n",
      "Length: 30\n",
      "Expected 43.5\n",
      "Result: 43.5\n",
      "Total passed to tested ratio: 4/4\n",
      "\n",
      "TEST #5:\n",
      "Input: [43, 60, 52, 7, 41, 51, 29, 28, 39, 41, 51, 43, 31, 5, 59, 43, 99, 1, 54]\n",
      "Sorted: [1, 5, 7, 28, 29, 31, 39, 41, 41, 43, 43, 43, 51, 51, 52, 54, 59, 60, 99]\n",
      "Length: 19\n",
      "Expected 43\n",
      "Result: 43\n",
      "Total passed to tested ratio: 5/5\n",
      "\n",
      "TEST #6:\n",
      "Input: [86, 53, 61, 16, 41, 13, 9, 30, 39, 40, 59, 73, 69, 90, 76, 18, 17, 41, 37, 37, 59, 99]\n",
      "Sorted: [9, 13, 16, 17, 18, 30, 37, 37, 39, 40, 41, 41, 53, 59, 59, 61, 69, 73, 76, 86, 90, 99]\n",
      "Length: 22\n",
      "Expected 41.0\n",
      "Result: 41\n",
      "Total passed to tested ratio: 6/6\n",
      "\n",
      "TEST #7:\n",
      "Input: [92, 89, 100, 73, 43, 18, 46, 0, 55, 43, 83, 12, 44, 17, 54, 98, 0, 87, 24, 79, 75, 48, 45, 76, 87, 8]\n",
      "Sorted: [0, 0, 8, 12, 17, 18, 24, 43, 43, 44, 45, 46, 48, 54, 55, 73, 75, 76, 79, 83, 87, 87, 89, 92, 98, 100]\n",
      "Length: 26\n",
      "Expected 51.0\n",
      "Result: 51\n",
      "Total passed to tested ratio: 7/7\n",
      "\n",
      "TEST #8:\n",
      "Input: [69, 54, 84, 54, 2, 29, 61, 100, 23, 0, 17, 24, 13, 1, 6, 75, 68, 20, 85, 73, 33, 49]\n",
      "Sorted: [0, 1, 2, 6, 13, 17, 20, 23, 24, 29, 33, 49, 54, 54, 61, 68, 69, 73, 75, 84, 85, 100]\n",
      "Length: 22\n",
      "Expected 41.0\n",
      "Result: 41\n",
      "Total passed to tested ratio: 8/8\n",
      "\n",
      "TEST #9:\n",
      "Input: [25, 90, 66, 94]\n",
      "Sorted: [25, 66, 90, 94]\n",
      "Length: 4\n",
      "Expected 78.0\n",
      "Result: 78\n",
      "Total passed to tested ratio: 9/9\n",
      "\n",
      "TEST #10:\n",
      "Input: [34, 58, 21, 22, 6, 42]\n",
      "Sorted: [6, 21, 22, 34, 42, 58]\n",
      "Length: 6\n",
      "Expected 28.0\n",
      "Result: 28\n",
      "Total passed to tested ratio: 10/10\n",
      "\n",
      "TEST #11:\n",
      "Input: [49, 19, 35, 17, 21, 32, 42, 100, 17, 54, 8, 85, 70, 65, 23, 55, 44, 90, 15, 98]\n",
      "Sorted: [8, 15, 17, 17, 19, 21, 23, 32, 35, 42, 44, 49, 54, 55, 65, 70, 85, 90, 98, 100]\n",
      "Length: 20\n",
      "Expected 43.0\n",
      "Result: 43\n",
      "Total passed to tested ratio: 11/11\n",
      "\n",
      "TEST #12:\n",
      "Input: [1]\n",
      "Sorted: [1]\n",
      "Length: 1\n",
      "Expected 1\n",
      "Result: 1\n",
      "Total passed to tested ratio: 12/12\n",
      "\n",
      "TEST #13:\n",
      "Input: [72, 24, 76, 42, 89, 38, 96, 96, 61]\n",
      "Sorted: [24, 38, 42, 61, 72, 76, 89, 96, 96]\n",
      "Length: 9\n",
      "Expected 72\n",
      "Result: 72\n",
      "Total passed to tested ratio: 13/13\n",
      "\n",
      "TEST #14:\n",
      "Input: [90, 99]\n",
      "Sorted: [90, 99]\n",
      "Length: 2\n",
      "Expected 94.5\n",
      "Result: 94.5\n",
      "Total passed to tested ratio: 14/14\n",
      "\n",
      "TEST #15:\n",
      "Input: [67, 26, 34, 40, 39, 62, 20, 41, 41, 46]\n",
      "Sorted: [20, 26, 34, 39, 40, 41, 41, 46, 62, 67]\n",
      "Length: 10\n",
      "Expected 40.5\n",
      "Result: 40.5\n",
      "Total passed to tested ratio: 15/15\n",
      "\n",
      "TEST #16:\n",
      "Input: [70, 46]\n",
      "Sorted: [46, 70]\n",
      "Length: 2\n",
      "Expected 58.0\n",
      "Result: 58\n",
      "Total passed to tested ratio: 16/16\n",
      "\n",
      "TEST #17:\n",
      "Input: [56, 28, 74, 96, 63, 93, 4, 43, 63, 11, 2, 69, 69, 61]\n",
      "Sorted: [2, 4, 11, 28, 43, 56, 61, 63, 63, 69, 69, 74, 93, 96]\n",
      "Length: 14\n",
      "Expected 62.0\n",
      "Result: 62\n",
      "Total passed to tested ratio: 17/17\n",
      "\n",
      "TEST #18:\n",
      "Input: [7, 18, 91, 63, 10, 52, 46, 24, 66, 19, 52, 47, 79, 38, 2, 7, 55, 88]\n",
      "Sorted: [2, 7, 7, 10, 18, 19, 24, 38, 46, 47, 52, 52, 55, 63, 66, 79, 88, 91]\n",
      "Length: 18\n",
      "Expected 46.5\n",
      "Result: 46.5\n",
      "Total passed to tested ratio: 18/18\n",
      "\n",
      "TEST #19:\n",
      "Input: [63, 100, 14, 88, 38, 77, 82, 71, 37]\n",
      "Sorted: [14, 37, 38, 63, 71, 77, 82, 88, 100]\n",
      "Length: 9\n",
      "Expected 71\n",
      "Result: 71\n",
      "Total passed to tested ratio: 19/19\n",
      "\n",
      "TEST #20:\n",
      "Input: [47, 64, 86, 63, 7, 42, 20, 38, 97, 12, 30, 15, 3, 26, 45, 5, 14, 86, 72, 84, 59, 80, 5, 72, 18, 48, 36, 8, 64]\n",
      "Sorted: [3, 5, 5, 7, 8, 12, 14, 15, 18, 20, 26, 30, 36, 38, 42, 45, 47, 48, 59, 63, 64, 64, 72, 72, 80, 84, 86, 86, 97]\n",
      "Length: 29\n",
      "Expected 42\n",
      "Result: 42\n",
      "Total passed to tested ratio: 20/20\n",
      "\n",
      "TEST #21:\n",
      "Input: [62, 100, 30, 13, 50, 27, 41, 13, 0, 40, 52, 46, 44, 98, 66, 83, 45, 2, 88, 95, 20]\n",
      "Sorted: [0, 2, 13, 13, 20, 27, 30, 40, 41, 44, 45, 46, 50, 52, 62, 66, 83, 88, 95, 98, 100]\n",
      "Length: 21\n",
      "Expected 45\n",
      "Result: 45\n",
      "Total passed to tested ratio: 21/21\n",
      "\n",
      "TEST #22:\n",
      "Input: [87, 59, 64, 39, 63, 61, 68, 5, 18, 88, 98, 48, 19, 68, 49, 5, 64, 99, 53, 20, 81, 0, 40, 86, 88, 61, 56, 61, 19, 28]\n",
      "Sorted: [0, 5, 5, 18, 19, 19, 20, 28, 39, 40, 48, 49, 53, 56, 59, 61, 61, 61, 63, 64, 64, 68, 68, 81, 86, 87, 88, 88, 98, 99]\n",
      "Length: 30\n",
      "Expected 60.0\n",
      "Result: 60\n",
      "Total passed to tested ratio: 22/22\n",
      "\n",
      "TEST #23:\n",
      "Input: [18, 57, 4, 30, 61, 28, 87, 69, 49, 94, 2, 5, 50, 68, 68, 46, 7, 23, 46, 57, 46, 50, 49, 54, 67]\n",
      "Sorted: [2, 4, 5, 7, 18, 23, 28, 30, 46, 46, 46, 49, 49, 50, 50, 54, 57, 57, 61, 67, 68, 68, 69, 87, 94]\n",
      "Length: 25\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 23/23\n",
      "\n",
      "TEST #24:\n",
      "Input: [79, 21, 36, 43, 1, 35, 0, 82, 40, 71, 94, 62, 6, 12, 34, 16, 37, 62, 100, 76]\n",
      "Sorted: [0, 1, 6, 12, 16, 21, 34, 35, 36, 37, 40, 43, 62, 62, 71, 76, 79, 82, 94, 100]\n",
      "Length: 20\n",
      "Expected 38.5\n",
      "Result: 38.5\n",
      "Total passed to tested ratio: 24/24\n",
      "\n",
      "TEST #25:\n",
      "Input: [31, 56, 8, 50, 54, 69, 41, 43, 65, 66, 35, 27, 9, 5, 59, 44, 14, 53, 33, 14, 91, 63, 73, 35, 92, 1, 57]\n",
      "Sorted: [1, 5, 8, 9, 14, 14, 27, 31, 33, 35, 35, 41, 43, 44, 50, 53, 54, 56, 57, 59, 63, 65, 66, 69, 73, 91, 92]\n",
      "Length: 27\n",
      "Expected 44\n",
      "Result: 44\n",
      "Total passed to tested ratio: 25/25\n",
      "\n",
      "TEST #26:\n",
      "Input: [16, 12, 63, 87, 8, 18, 12, 3, 55, 20, 17, 19, 23, 86, 38, 77, 74, 21]\n",
      "Sorted: [3, 8, 12, 12, 16, 17, 18, 19, 20, 21, 23, 38, 55, 63, 74, 77, 86, 87]\n",
      "Length: 18\n",
      "Expected 20.5\n",
      "Result: 20.5\n",
      "Total passed to tested ratio: 26/26\n",
      "\n",
      "TEST #27:\n",
      "Input: [89, 74, 90, 9, 68, 43, 90, 91, 22, 53]\n",
      "Sorted: [9, 22, 43, 53, 68, 74, 89, 90, 90, 91]\n",
      "Length: 10\n",
      "Expected 71.0\n",
      "Result: 71\n",
      "Total passed to tested ratio: 27/27\n",
      "\n",
      "TEST #28:\n",
      "Input: [5, 75, 18, 73, 68, 78, 87, 84, 44, 93, 81, 93, 58, 100, 43, 62, 76, 56, 35, 81, 86, 55, 25, 6, 6, 51, 54, 70, 27, 41]\n",
      "Sorted: [5, 6, 6, 18, 25, 27, 35, 41, 43, 44, 51, 54, 55, 56, 58, 62, 68, 70, 73, 75, 76, 78, 81, 81, 84, 86, 87, 93, 93, 100]\n",
      "Length: 30\n",
      "Expected 60.0\n",
      "Result: 60\n",
      "Total passed to tested ratio: 28/28\n",
      "\n",
      "TEST #29:\n",
      "Input: [17, 81, 28, 63, 41, 19, 58, 63, 32, 52, 30, 27, 16, 30, 78, 23, 60, 79, 33, 27, 77, 46, 54, 19, 90, 49, 86, 31, 80]\n",
      "Sorted: [16, 17, 19, 19, 23, 27, 27, 28, 30, 30, 31, 32, 33, 41, 46, 49, 52, 54, 58, 60, 63, 63, 77, 78, 79, 80, 81, 86, 90]\n",
      "Length: 29\n",
      "Expected 46\n",
      "Result: 46\n",
      "Total passed to tested ratio: 29/29\n",
      "\n",
      "TEST #30:\n",
      "Input: [55, 2, 82, 52, 73, 30, 48, 87, 22, 2, 17, 14, 79, 19]\n",
      "Sorted: [2, 2, 14, 17, 19, 22, 30, 48, 52, 55, 73, 79, 82, 87]\n",
      "Length: 14\n",
      "Expected 39.0\n",
      "Result: 39\n",
      "Total passed to tested ratio: 30/30\n",
      "\n",
      "TEST #31:\n",
      "Input: [58, 2, 81, 42, 61, 23, 76, 63, 64, 10]\n",
      "Sorted: [2, 10, 23, 42, 58, 61, 63, 64, 76, 81]\n",
      "Length: 10\n",
      "Expected 59.5\n",
      "Result: 59.5\n",
      "Total passed to tested ratio: 31/31\n",
      "\n",
      "TEST #32:\n",
      "Input: [14, 25, 79, 40, 65, 87, 73, 69, 72, 6, 0, 90, 82, 5, 9, 92, 87, 50]\n",
      "Sorted: [0, 5, 6, 9, 14, 25, 40, 50, 65, 69, 72, 73, 79, 82, 87, 87, 90, 92]\n",
      "Length: 18\n",
      "Expected 67.0\n",
      "Result: 67\n",
      "Total passed to tested ratio: 32/32\n",
      "\n",
      "TEST #33:\n",
      "Input: [95, 22, 23, 35, 44, 64, 95, 69, 20, 47, 32]\n",
      "Sorted: [20, 22, 23, 32, 35, 44, 47, 64, 69, 95, 95]\n",
      "Length: 11\n",
      "Expected 44\n",
      "Result: 44\n",
      "Total passed to tested ratio: 33/33\n",
      "\n",
      "TEST #34:\n",
      "Input: [35, 81, 38, 45, 64, 23, 28, 53, 36, 19, 81, 16, 27, 37, 72, 22, 79, 7, 40, 28, 34, 100, 65, 6, 67, 29, 65, 97, 77, 30]\n",
      "Sorted: [6, 7, 16, 19, 22, 23, 27, 28, 28, 29, 30, 34, 35, 36, 37, 38, 40, 45, 53, 64, 65, 65, 67, 72, 77, 79, 81, 81, 97, 100]\n",
      "Length: 30\n",
      "Expected 37.5\n",
      "Result: 37.5\n",
      "Total passed to tested ratio: 34/34\n",
      "\n",
      "TEST #35:\n",
      "Input: [86, 47, 16, 82, 31, 81, 42, 17, 80, 26, 60, 12, 83, 42, 53, 24, 0, 30, 33, 36, 75, 21, 67, 26, 90, 27, 66, 85, 85]\n",
      "Sorted: [0, 12, 16, 17, 21, 24, 26, 26, 27, 30, 31, 33, 36, 42, 42, 47, 53, 60, 66, 67, 75, 80, 81, 82, 83, 85, 85, 86, 90]\n",
      "Length: 29\n",
      "Expected 42\n",
      "Result: 42\n",
      "Total passed to tested ratio: 35/35\n",
      "\n",
      "TEST #36:\n",
      "Input: [53, 40, 48, 15, 31, 13, 82, 21, 90, 49, 47, 91, 66, 70, 71]\n",
      "Sorted: [13, 15, 21, 31, 40, 47, 48, 49, 53, 66, 70, 71, 82, 90, 91]\n",
      "Length: 15\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 36/36\n",
      "\n",
      "TEST #37:\n",
      "Input: [41, 15, 28, 8, 67, 100, 53, 74, 90, 46, 60, 97, 55, 23, 20, 81, 85, 46, 34, 48, 96, 36, 34, 93, 95, 55, 87, 53]\n",
      "Sorted: [8, 15, 20, 23, 28, 34, 34, 36, 41, 46, 46, 48, 53, 53, 55, 55, 60, 67, 74, 81, 85, 87, 90, 93, 95, 96, 97, 100]\n",
      "Length: 28\n",
      "Expected 54.0\n",
      "Result: 54\n",
      "Total passed to tested ratio: 37/37\n",
      "\n",
      "TEST #38:\n",
      "Input: [7, 28, 6, 68, 93, 56, 46, 22, 98, 76, 94, 72, 19, 19, 69, 35, 5, 47, 31, 71, 91, 67, 13, 30, 39, 23]\n",
      "Sorted: [5, 6, 7, 13, 19, 19, 22, 23, 28, 30, 31, 35, 39, 46, 47, 56, 67, 68, 69, 71, 72, 76, 91, 93, 94, 98]\n",
      "Length: 26\n",
      "Expected 42.5\n",
      "Result: 42.5\n",
      "Total passed to tested ratio: 38/38\n",
      "\n",
      "TEST #39:\n",
      "Input: [23, 21, 35, 39, 44, 71, 66, 29, 42, 3, 63]\n",
      "Sorted: [3, 21, 23, 29, 35, 39, 42, 44, 63, 66, 71]\n",
      "Length: 11\n",
      "Expected 39\n",
      "Result: 39\n",
      "Total passed to tested ratio: 39/39\n",
      "\n",
      "TEST #40:\n",
      "Input: [58, 85, 12, 22, 57, 96, 70, 86, 43, 44, 10, 83, 10, 78, 52, 17, 66, 31, 100]\n",
      "Sorted: [10, 10, 12, 17, 22, 31, 43, 44, 52, 57, 58, 66, 70, 78, 83, 85, 86, 96, 100]\n",
      "Length: 19\n",
      "Expected 57\n",
      "Result: 57\n",
      "Total passed to tested ratio: 40/40\n",
      "\n",
      "TEST #41:\n",
      "Input: [51, 73, 10, 23, 84, 8, 61]\n",
      "Sorted: [8, 10, 23, 51, 61, 73, 84]\n",
      "Length: 7\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 41/41\n",
      "\n",
      "TEST #42:\n",
      "Input: [86, 3, 70, 68, 75, 5, 31, 51, 68, 25, 68, 79, 67, 86, 72, 32, 64, 27, 41, 87, 82, 100, 26]\n",
      "Sorted: [3, 5, 25, 26, 27, 31, 32, 41, 51, 64, 67, 68, 68, 68, 70, 72, 75, 79, 82, 86, 86, 87, 100]\n",
      "Length: 23\n",
      "Expected 68\n",
      "Result: 68\n",
      "Total passed to tested ratio: 42/42\n",
      "\n",
      "TEST #43:\n",
      "Input: [70, 84, 72, 72, 0, 42, 45, 89, 92, 97, 54, 79]\n",
      "Sorted: [0, 42, 45, 54, 70, 72, 72, 79, 84, 89, 92, 97]\n",
      "Length: 12\n",
      "Expected 72.0\n",
      "Result: 72\n",
      "Total passed to tested ratio: 43/43\n",
      "\n",
      "TEST #44:\n",
      "Input: [94, 24, 7, 16, 6]\n",
      "Sorted: [6, 7, 16, 24, 94]\n",
      "Length: 5\n",
      "Expected 16\n",
      "Result: 16\n",
      "Total passed to tested ratio: 44/44\n",
      "\n",
      "TEST #45:\n",
      "Input: [86, 74, 13, 80, 23, 51, 14, 67, 45, 37, 14, 65, 81, 21, 29, 24, 70, 85, 34, 83, 36, 25, 6, 29, 38, 49, 78]\n",
      "Sorted: [6, 13, 14, 14, 21, 23, 24, 25, 29, 29, 34, 36, 37, 38, 45, 49, 51, 65, 67, 70, 74, 78, 80, 81, 83, 85, 86]\n",
      "Length: 27\n",
      "Expected 38\n",
      "Result: 38\n",
      "Total passed to tested ratio: 45/45\n",
      "\n",
      "TEST #46:\n",
      "Input: [10, 71, 45]\n",
      "Sorted: [10, 45, 71]\n",
      "Length: 3\n",
      "Expected 45\n",
      "Result: 45\n",
      "Total passed to tested ratio: 46/46\n",
      "\n",
      "TEST #47:\n",
      "Input: [27, 21, 95, 11, 51, 58, 67, 55, 69]\n",
      "Sorted: [11, 21, 27, 51, 55, 58, 67, 69, 95]\n",
      "Length: 9\n",
      "Expected 55\n",
      "Result: 55\n",
      "Total passed to tested ratio: 47/47\n",
      "\n",
      "TEST #48:\n",
      "Input: [94, 69, 23, 60, 42, 31]\n",
      "Sorted: [23, 31, 42, 60, 69, 94]\n",
      "Length: 6\n",
      "Expected 51.0\n",
      "Result: 51\n",
      "Total passed to tested ratio: 48/48\n",
      "\n",
      "TEST #49:\n",
      "Input: [96, 70, 12, 47, 18, 93, 41, 66, 72, 68, 59, 46]\n",
      "Sorted: [12, 18, 41, 46, 47, 59, 66, 68, 70, 72, 93, 96]\n",
      "Length: 12\n",
      "Expected 62.5\n",
      "Result: 62.5\n",
      "Total passed to tested ratio: 49/49\n",
      "\n",
      "TEST #50:\n",
      "Input: [17, 92, 97, 32, 11, 64, 61, 80, 50, 74, 51, 13, 74, 97, 80, 65, 33]\n",
      "Sorted: [11, 13, 17, 32, 33, 50, 51, 61, 64, 65, 74, 74, 80, 80, 92, 97, 97]\n",
      "Length: 17\n",
      "Expected 64\n",
      "Result: 64\n",
      "Total passed to tested ratio: 50/50\n",
      "\n",
      "TEST #51:\n",
      "Input: [1, 57, 79, 54, 85, 55, 30, 87, 73, 0, 29]\n",
      "Sorted: [0, 1, 29, 30, 54, 55, 57, 73, 79, 85, 87]\n",
      "Length: 11\n",
      "Expected 55\n",
      "Result: 55\n",
      "Total passed to tested ratio: 51/51\n",
      "\n",
      "TEST #52:\n",
      "Input: [43, 40, 90]\n",
      "Sorted: [40, 43, 90]\n",
      "Length: 3\n",
      "Expected 43\n",
      "Result: 43\n",
      "Total passed to tested ratio: 52/52\n",
      "\n",
      "TEST #53:\n",
      "Input: [79, 34, 22, 97, 61, 77]\n",
      "Sorted: [22, 34, 61, 77, 79, 97]\n",
      "Length: 6\n",
      "Expected 69.0\n",
      "Result: 69\n",
      "Total passed to tested ratio: 53/53\n",
      "\n",
      "TEST #54:\n",
      "Input: [14, 79, 8, 98, 23, 85, 55, 31, 89, 26, 56, 38, 75, 22, 4, 88, 89, 86, 57, 65, 81]\n",
      "Sorted: [4, 8, 14, 22, 23, 26, 31, 38, 55, 56, 57, 65, 75, 79, 81, 85, 86, 88, 89, 89, 98]\n",
      "Length: 21\n",
      "Expected 57\n",
      "Result: 57\n",
      "Total passed to tested ratio: 54/54\n",
      "\n",
      "TEST #55:\n",
      "Input: [30, 43, 95, 94, 9, 64, 52, 93, 37, 59, 9, 60, 60, 23, 77, 65, 8, 77]\n",
      "Sorted: [8, 9, 9, 23, 30, 37, 43, 52, 59, 60, 60, 64, 65, 77, 77, 93, 94, 95]\n",
      "Length: 18\n",
      "Expected 59.5\n",
      "Result: 59.5\n",
      "Total passed to tested ratio: 55/55\n",
      "\n",
      "TEST #56:\n",
      "Input: [2, 97, 66, 63, 15, 60, 66, 96, 99, 26, 0, 12]\n",
      "Sorted: [0, 2, 12, 15, 26, 60, 63, 66, 66, 96, 97, 99]\n",
      "Length: 12\n",
      "Expected 61.5\n",
      "Result: 61.5\n",
      "Total passed to tested ratio: 56/56\n",
      "\n",
      "TEST #57:\n",
      "Input: [14, 88, 27, 75, 58, 45, 38, 32, 1, 67, 58, 54]\n",
      "Sorted: [1, 14, 27, 32, 38, 45, 54, 58, 58, 67, 75, 88]\n",
      "Length: 12\n",
      "Expected 49.5\n",
      "Result: 49.5\n",
      "Total passed to tested ratio: 57/57\n",
      "\n",
      "TEST #58:\n",
      "Input: [77, 59, 93, 46, 86, 38, 72, 37, 27, 73, 90, 63, 10, 46, 92]\n",
      "Sorted: [10, 27, 37, 38, 46, 46, 59, 63, 72, 73, 77, 86, 90, 92, 93]\n",
      "Length: 15\n",
      "Expected 63\n",
      "Result: 63\n",
      "Total passed to tested ratio: 58/58\n",
      "\n",
      "TEST #59:\n",
      "Input: [97, 37, 50, 80, 47, 32, 36, 33]\n",
      "Sorted: [32, 33, 36, 37, 47, 50, 80, 97]\n",
      "Length: 8\n",
      "Expected 42.0\n",
      "Result: 42\n",
      "Total passed to tested ratio: 59/59\n",
      "\n",
      "TEST #60:\n",
      "Input: [42, 74, 40, 69, 14, 16, 51, 98, 23, 94, 53, 55, 71, 27, 88, 67, 11, 70, 93, 42, 18, 28, 10, 59, 6, 64, 23]\n",
      "Sorted: [6, 10, 11, 14, 16, 18, 23, 23, 27, 28, 40, 42, 42, 51, 53, 55, 59, 64, 67, 69, 70, 71, 74, 88, 93, 94, 98]\n",
      "Length: 27\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 60/60\n",
      "\n",
      "TEST #61:\n",
      "Input: [86, 79, 76, 3, 99, 64, 35, 75, 19, 40, 27, 68, 75, 30, 29, 64, 33, 1, 99, 61, 4]\n",
      "Sorted: [1, 3, 4, 19, 27, 29, 30, 33, 35, 40, 61, 64, 64, 68, 75, 75, 76, 79, 86, 99, 99]\n",
      "Length: 21\n",
      "Expected 61\n",
      "Result: 61\n",
      "Total passed to tested ratio: 61/61\n",
      "\n",
      "TEST #62:\n",
      "Input: [78, 2, 80, 3, 72, 50, 89, 13, 52, 65, 44]\n",
      "Sorted: [2, 3, 13, 44, 50, 52, 65, 72, 78, 80, 89]\n",
      "Length: 11\n",
      "Expected 52\n",
      "Result: 52\n",
      "Total passed to tested ratio: 62/62\n",
      "\n",
      "TEST #63:\n",
      "Input: [37, 3, 52, 10, 50, 5, 91, 25, 17, 50]\n",
      "Sorted: [3, 5, 10, 17, 25, 37, 50, 50, 52, 91]\n",
      "Length: 10\n",
      "Expected 31.0\n",
      "Result: 31\n",
      "Total passed to tested ratio: 63/63\n",
      "\n",
      "TEST #64:\n",
      "Input: [40, 22, 11, 34]\n",
      "Sorted: [11, 22, 34, 40]\n",
      "Length: 4\n",
      "Expected 28.0\n",
      "Result: 28\n",
      "Total passed to tested ratio: 64/64\n",
      "\n",
      "TEST #65:\n",
      "Input: [45, 42, 53, 42, 49, 7, 91, 92, 80, 86, 76, 47, 83, 19, 26, 1, 94, 32, 5, 86, 89, 80, 88, 22, 35]\n",
      "Sorted: [1, 5, 7, 19, 22, 26, 32, 35, 42, 42, 45, 47, 49, 53, 76, 80, 80, 83, 86, 86, 88, 89, 91, 92, 94]\n",
      "Length: 25\n",
      "Expected 49\n",
      "Result: 49\n",
      "Total passed to tested ratio: 65/65\n",
      "\n",
      "TEST #66:\n",
      "Input: []\n",
      "Sorted: []\n",
      "Length: 0\n",
      "Expected None\n",
      "Result: None\n",
      "Total passed to tested ratio: 66/66\n",
      "\n",
      "TEST #67:\n",
      "Input: [1, 7, 23, 43, 83, 61, 56, 25, 67, 19, 81, 27, 88]\n",
      "Sorted: [1, 7, 19, 23, 25, 27, 43, 56, 61, 67, 81, 83, 88]\n",
      "Length: 13\n",
      "Expected 43\n",
      "Result: 43\n",
      "Total passed to tested ratio: 67/67\n",
      "\n",
      "TEST #68:\n",
      "Input: [88, 50]\n",
      "Sorted: [50, 88]\n",
      "Length: 2\n",
      "Expected 69.0\n",
      "Result: 69\n",
      "Total passed to tested ratio: 68/68\n",
      "\n",
      "TEST #69:\n",
      "Input: [87, 52, 89, 46, 71, 55, 81, 91, 23, 88, 57, 72, 85, 19, 71, 26, 73, 56, 69, 9, 27, 65, 99, 25, 7, 92, 11]\n",
      "Sorted: [7, 9, 11, 19, 23, 25, 26, 27, 46, 52, 55, 56, 57, 65, 69, 71, 71, 72, 73, 81, 85, 87, 88, 89, 91, 92, 99]\n",
      "Length: 27\n",
      "Expected 65\n",
      "Result: 65\n",
      "Total passed to tested ratio: 69/69\n",
      "\n",
      "TEST #70:\n",
      "Input: [21, 62, 75, 96, 25, 99, 73, 69, 61, 66, 7, 25, 29, 88, 39, 32, 64, 30, 16, 31, 99, 50, 71, 67, 95, 89]\n",
      "Sorted: [7, 16, 21, 25, 25, 29, 30, 31, 32, 39, 50, 61, 62, 64, 66, 67, 69, 71, 73, 75, 88, 89, 95, 96, 99, 99]\n",
      "Length: 26\n",
      "Expected 63.0\n",
      "Result: 63\n",
      "Total passed to tested ratio: 70/70\n",
      "\n",
      "TEST #71:\n",
      "Input: [36, 55, 8, 29, 44, 66, 12, 14, 69, 77, 72, 22, 68, 88, 68, 3, 89, 13, 33, 91, 25, 3, 77]\n",
      "Sorted: [3, 3, 8, 12, 13, 14, 22, 25, 29, 33, 36, 44, 55, 66, 68, 68, 69, 72, 77, 77, 88, 89, 91]\n",
      "Length: 23\n",
      "Expected 44\n",
      "Result: 44\n",
      "Total passed to tested ratio: 71/71\n",
      "\n",
      "TEST #72:\n",
      "Input: [51, 100, 41, 45, 70, 77, 61, 29, 37, 43, 56, 6, 17, 52, 97, 1, 77, 40, 62]\n",
      "Sorted: [1, 6, 17, 29, 37, 40, 41, 43, 45, 51, 52, 56, 61, 62, 70, 77, 77, 97, 100]\n",
      "Length: 19\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 72/72\n",
      "\n",
      "TEST #73:\n",
      "Input: [31, 73, 5]\n",
      "Sorted: [5, 31, 73]\n",
      "Length: 3\n",
      "Expected 31\n",
      "Result: 31\n",
      "Total passed to tested ratio: 73/73\n",
      "\n",
      "TEST #74:\n",
      "Input: [78, 98, 69, 2, 30, 1, 86, 62, 43, 87]\n",
      "Sorted: [1, 2, 30, 43, 62, 69, 78, 86, 87, 98]\n",
      "Length: 10\n",
      "Expected 65.5\n",
      "Result: 65.5\n",
      "Total passed to tested ratio: 74/74\n",
      "\n",
      "TEST #75:\n",
      "Input: [37, 74, 36, 28, 13, 18, 35, 86, 57]\n",
      "Sorted: [13, 18, 28, 35, 36, 37, 57, 74, 86]\n",
      "Length: 9\n",
      "Expected 36\n",
      "Result: 36\n",
      "Total passed to tested ratio: 75/75\n",
      "\n",
      "TEST #76:\n",
      "Input: [78, 4, 57, 14, 47, 97, 5, 50, 43, 69, 72, 66, 61, 37, 44, 8, 48, 90, 67, 65]\n",
      "Sorted: [4, 5, 8, 14, 37, 43, 44, 47, 48, 50, 57, 61, 65, 66, 67, 69, 72, 78, 90, 97]\n",
      "Length: 20\n",
      "Expected 53.5\n",
      "Result: 53.5\n",
      "Total passed to tested ratio: 76/76\n",
      "\n",
      "TEST #77:\n",
      "Input: [98, 100, 75, 94, 1, 39, 98, 72, 84, 98, 79, 66, 86]\n",
      "Sorted: [1, 39, 66, 72, 75, 79, 84, 86, 94, 98, 98, 98, 100]\n",
      "Length: 13\n",
      "Expected 84\n",
      "Result: 84\n",
      "Total passed to tested ratio: 77/77\n",
      "\n",
      "TEST #78:\n",
      "Input: [5, 48, 69, 97, 12, 83, 65, 72, 19, 36, 56, 58, 21, 43, 63, 13]\n",
      "Sorted: [5, 12, 13, 19, 21, 36, 43, 48, 56, 58, 63, 65, 69, 72, 83, 97]\n",
      "Length: 16\n",
      "Expected 52.0\n",
      "Result: 52\n",
      "Total passed to tested ratio: 78/78\n",
      "\n",
      "TEST #79:\n",
      "Input: [13]\n",
      "Sorted: [13]\n",
      "Length: 1\n",
      "Expected 13\n",
      "Result: 13\n",
      "Total passed to tested ratio: 79/79\n",
      "\n",
      "TEST #80:\n",
      "Input: [54, 86, 45, 82, 80, 58, 68, 73, 92, 60, 28, 82, 12, 50, 26, 21]\n",
      "Sorted: [12, 21, 26, 28, 45, 50, 54, 58, 60, 68, 73, 80, 82, 82, 86, 92]\n",
      "Length: 16\n",
      "Expected 59.0\n",
      "Result: 59\n",
      "Total passed to tested ratio: 80/80\n",
      "\n",
      "TEST #81:\n",
      "Input: [26, 33, 29, 17, 93, 14, 13, 85, 52, 46, 41, 5, 46, 0, 17, 0, 60]\n",
      "Sorted: [0, 0, 5, 13, 14, 17, 17, 26, 29, 33, 41, 46, 46, 52, 60, 85, 93]\n",
      "Length: 17\n",
      "Expected 29\n",
      "Result: 29\n",
      "Total passed to tested ratio: 81/81\n",
      "\n",
      "TEST #82:\n",
      "Input: [92, 74, 42, 24, 66, 74, 7, 86, 21, 82, 52, 98, 30, 12, 15, 94, 15, 78, 37, 81]\n",
      "Sorted: [7, 12, 15, 15, 21, 24, 30, 37, 42, 52, 66, 74, 74, 78, 81, 82, 86, 92, 94, 98]\n",
      "Length: 20\n",
      "Expected 59.0\n",
      "Result: 59\n",
      "Total passed to tested ratio: 82/82\n",
      "\n",
      "TEST #83:\n",
      "Input: [35, 41, 81, 40, 77, 3, 56, 28, 3, 60, 64, 95, 52, 13, 72, 94, 2, 64]\n",
      "Sorted: [2, 3, 3, 13, 28, 35, 40, 41, 52, 56, 60, 64, 64, 72, 77, 81, 94, 95]\n",
      "Length: 18\n",
      "Expected 54.0\n",
      "Result: 54\n",
      "Total passed to tested ratio: 83/83\n",
      "\n",
      "TEST #84:\n",
      "Input: [98, 73, 50, 47, 58, 92, 68, 75, 28, 17, 46, 86, 33]\n",
      "Sorted: [17, 28, 33, 46, 47, 50, 58, 68, 73, 75, 86, 92, 98]\n",
      "Length: 13\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 84/84\n",
      "\n",
      "TEST #85:\n",
      "Input: [31, 8, 14, 99, 88, 53, 56, 8, 91, 4, 26, 19, 81, 71, 12, 7, 55, 18, 55, 50, 32, 44, 28, 47]\n",
      "Sorted: [4, 7, 8, 8, 12, 14, 18, 19, 26, 28, 31, 32, 44, 47, 50, 53, 55, 55, 56, 71, 81, 88, 91, 99]\n",
      "Length: 24\n",
      "Expected 38.0\n",
      "Result: 38\n",
      "Total passed to tested ratio: 85/85\n",
      "\n",
      "TEST #86:\n",
      "Input: [74, 46, 76, 29, 45, 5, 68, 3, 50, 57, 28, 37, 22, 27, 58, 40, 70, 82, 67]\n",
      "Sorted: [3, 5, 22, 27, 28, 29, 37, 40, 45, 46, 50, 57, 58, 67, 68, 70, 74, 76, 82]\n",
      "Length: 19\n",
      "Expected 46\n",
      "Result: 46\n",
      "Total passed to tested ratio: 86/86\n",
      "\n",
      "TEST #87:\n",
      "Input: []\n",
      "Sorted: []\n",
      "Length: 0\n",
      "Expected None\n",
      "Result: None\n",
      "Total passed to tested ratio: 87/87\n",
      "\n",
      "TEST #88:\n",
      "Input: [23, 95, 14, 55, 10, 22, 22, 8]\n",
      "Sorted: [8, 10, 14, 22, 22, 23, 55, 95]\n",
      "Length: 8\n",
      "Expected 22.0\n",
      "Result: 22\n",
      "Total passed to tested ratio: 88/88\n",
      "\n",
      "TEST #89:\n",
      "Input: [40, 92, 53, 53, 64, 24, 66]\n",
      "Sorted: [24, 40, 53, 53, 64, 66, 92]\n",
      "Length: 7\n",
      "Expected 53\n",
      "Result: 53\n",
      "Total passed to tested ratio: 89/89\n",
      "\n",
      "TEST #90:\n",
      "Input: [26, 19, 48, 66, 96, 39, 54, 94, 32, 8]\n",
      "Sorted: [8, 19, 26, 32, 39, 48, 54, 66, 94, 96]\n",
      "Length: 10\n",
      "Expected 43.5\n",
      "Result: 43.5\n",
      "Total passed to tested ratio: 90/90\n",
      "\n",
      "TEST #91:\n",
      "Input: [96, 8, 56, 28]\n",
      "Sorted: [8, 28, 56, 96]\n",
      "Length: 4\n",
      "Expected 42.0\n",
      "Result: 42\n",
      "Total passed to tested ratio: 91/91\n",
      "\n",
      "TEST #92:\n",
      "Input: [12, 51, 39, 93, 82, 22, 14, 91, 97, 63, 12, 55, 32, 12, 83, 38, 76]\n",
      "Sorted: [12, 12, 12, 14, 22, 32, 38, 39, 51, 55, 63, 76, 82, 83, 91, 93, 97]\n",
      "Length: 17\n",
      "Expected 51\n",
      "Result: 51\n",
      "Total passed to tested ratio: 92/92\n",
      "\n",
      "TEST #93:\n",
      "Input: [26]\n",
      "Sorted: [26]\n",
      "Length: 1\n",
      "Expected 26\n",
      "Result: 26\n",
      "Total passed to tested ratio: 93/93\n",
      "\n",
      "TEST #94:\n",
      "Input: [96, 69, 8, 74, 63, 92, 37, 49, 84, 97]\n",
      "Sorted: [8, 37, 49, 63, 69, 74, 84, 92, 96, 97]\n",
      "Length: 10\n",
      "Expected 71.5\n",
      "Result: 71.5\n",
      "Total passed to tested ratio: 94/94\n",
      "\n",
      "TEST #95:\n",
      "Input: [70, 39, 88, 17, 53, 59, 95, 2, 34, 13]\n",
      "Sorted: [2, 13, 17, 34, 39, 53, 59, 70, 88, 95]\n",
      "Length: 10\n",
      "Expected 46.0\n",
      "Result: 46\n",
      "Total passed to tested ratio: 95/95\n",
      "\n",
      "TEST #96:\n",
      "Input: [72, 6, 30, 77, 99, 3, 48, 73, 32, 34, 74, 8, 64, 96, 57, 12, 67, 96, 15, 54, 0, 63, 60, 39, 99]\n",
      "Sorted: [0, 3, 6, 8, 12, 15, 30, 32, 34, 39, 48, 54, 57, 60, 63, 64, 67, 72, 73, 74, 77, 96, 96, 99, 99]\n",
      "Length: 25\n",
      "Expected 57\n",
      "Result: 57\n",
      "Total passed to tested ratio: 96/96\n",
      "\n",
      "TEST #97:\n",
      "Input: [48, 38, 49, 87]\n",
      "Sorted: [38, 48, 49, 87]\n",
      "Length: 4\n",
      "Expected 48.5\n",
      "Result: 48.5\n",
      "Total passed to tested ratio: 97/97\n",
      "\n",
      "TEST #98:\n",
      "Input: [74, 13, 100, 88, 11, 11, 36, 73, 0, 3, 91, 36, 30, 79, 25, 33, 30, 69, 27, 42]\n",
      "Sorted: [0, 3, 11, 11, 13, 25, 27, 30, 30, 33, 36, 36, 42, 69, 73, 74, 79, 88, 91, 100]\n",
      "Length: 20\n",
      "Expected 34.5\n",
      "Result: 34.5\n",
      "Total passed to tested ratio: 98/98\n",
      "\n",
      "TEST #99:\n",
      "Input: [4, 74, 79, 44, 58, 37, 81, 4, 58, 54, 86, 95, 49, 88, 65, 47, 58, 58, 10, 81, 65]\n",
      "Sorted: [4, 4, 10, 37, 44, 47, 49, 54, 58, 58, 58, 58, 65, 65, 74, 79, 81, 81, 86, 88, 95]\n",
      "Length: 21\n",
      "Expected 58\n",
      "Result: 58\n",
      "Total passed to tested ratio: 99/99\n",
      "\n",
      "TEST #100:\n",
      "Input: [7, 10, 66, 63, 19, 100, 37, 71, 14, 67, 85, 36]\n",
      "Sorted: [7, 10, 14, 19, 36, 37, 63, 66, 67, 71, 85, 100]\n",
      "Length: 12\n",
      "Expected 50.0\n",
      "Result: 50\n",
      "Total passed to tested ratio: 100/100\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "samples = 100\n",
    "\n",
    "passed = 0\n",
    "for n in range(samples):\n",
    "    arr = [random.randint(0, 100) for _ in range(random.randint(0, 30))]\n",
    "    arr_sorted = sorted(arr)\n",
    "    center = len(arr) // 2\n",
    "    if len(arr) >= 2:\n",
    "        expected = arr_sorted[center] if len(arr) % 2 else (arr_sorted[center] + arr_sorted[center - 1]) / 2\n",
    "    elif len(arr) == 1:\n",
    "        expected = arr[0]\n",
    "    else:\n",
    "        expected = None\n",
    "    min_heap, max_heap = create_median_heap(arr)\n",
    "    result = get_median_from_median_heap(min_heap, max_heap)\n",
    "    is_correct = result == expected\n",
    "    passed += is_correct\n",
    "    print(f'TEST #{n + 1}:')\n",
    "    print('Input:', arr)\n",
    "    print('Sorted:', sorted(arr))\n",
    "    print('Length:', len(arr))\n",
    "    print('Expected', expected)\n",
    "    print('Result:', result)\n",
    "    print(f'Total passed to tested ratio: {passed}/{n + 1}')\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Max Heap\n",
      "      37\n",
      "     /  \\\n",
      "  19      36\n",
      "  /\\      /\n",
      "7   14  10\n",
      "\n",
      "Min Heap\n",
      "          63\n",
      "       /     \\\n",
      "    66          85\n",
      "   / \\         / \n",
      " 71    67   100\n",
      "\n",
      "Removed median: 50\n",
      "\n",
      "Max Heap\n",
      "      36\n",
      "     /  \\\n",
      "  19      10\n",
      "  /\\\n",
      "7   14\n",
      "\n",
      "Min Heap\n",
      "          66\n",
      "       /     \\\n",
      "    67          85\n",
      "   / \\\n",
      " 71   100\n",
      "\n",
      "Removed median: 51\n",
      "\n",
      "Max Heap\n",
      "      19\n",
      "     /  \\\n",
      "  14      10\n",
      "  /\n",
      "7 \n",
      "\n",
      "Min Heap\n",
      "          67\n",
      "       /     \\\n",
      "    71          85\n",
      "   / \n",
      "100\n",
      "\n",
      "Removed median: 43\n",
      "\n",
      "Max Heap\n",
      "  14\n",
      "  /\\\n",
      "7   10\n",
      "\n",
      "Min Heap\n",
      "    71\n",
      "   / \\\n",
      "100    85\n",
      "\n",
      "Removed median: 42.5\n",
      "\n",
      "Max Heap\n",
      "  10\n",
      "  /\n",
      "7 \n",
      "\n",
      "Min Heap\n",
      "    85\n",
      "   / \n",
      "100\n",
      "\n",
      "Removed median: 47.5\n",
      "\n",
      "Max Heap\n",
      "7\n",
      "\n",
      "Min Heap\n",
      "100\n",
      "\n",
      "Removed median: 53.5\n",
      "\n"
     ]
    }
   ],
   "source": [
    "while min_heap or max_heap:\n",
    "    print_median_heap(min_heap, max_heap)\n",
    "    print('\\nRemoved median:', remove_median_from_median_heap(min_heap, max_heap), end='\\n\\n')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}